| Task: | Fibonacci towers |
| Sender: | aalto26km_043 |
| Submission time: | 2026-11-16 17:46:36 +0200 |
| Language: | Rust (2021) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | details |
| #2 | ACCEPTED | 0.00 s | details |
| #3 | ACCEPTED | 0.00 s | details |
| #4 | ACCEPTED | 0.00 s | details |
| #5 | ACCEPTED | 0.00 s | details |
| #6 | ACCEPTED | 0.00 s | details |
| #7 | ACCEPTED | 0.00 s | details |
| #8 | ACCEPTED | 0.00 s | details |
| #9 | ACCEPTED | 0.00 s | details |
| #10 | ACCEPTED | 0.00 s | details |
| #11 | ACCEPTED | 0.00 s | details |
| #12 | ACCEPTED | 0.00 s | details |
| #13 | ACCEPTED | 0.00 s | details |
| #14 | ACCEPTED | 0.00 s | details |
| #15 | ACCEPTED | 0.00 s | details |
| #16 | ACCEPTED | 0.00 s | details |
| #17 | ACCEPTED | 0.00 s | details |
| #18 | ACCEPTED | 0.00 s | details |
| #19 | ACCEPTED | 0.00 s | details |
| #20 | ACCEPTED | 0.00 s | details |
| #21 | ACCEPTED | 0.00 s | details |
| #22 | ACCEPTED | 0.00 s | details |
| #23 | ACCEPTED | 0.00 s | details |
| #24 | ACCEPTED | 0.00 s | details |
| #25 | ACCEPTED | 0.00 s | details |
| #26 | ACCEPTED | 0.00 s | details |
| #27 | ACCEPTED | 0.00 s | details |
| #28 | ACCEPTED | 0.00 s | details |
| #29 | ACCEPTED | 0.00 s | details |
| #30 | ACCEPTED | 0.00 s | details |
| #31 | ACCEPTED | 0.00 s | details |
| #32 | ACCEPTED | 0.00 s | details |
| #33 | ACCEPTED | 0.00 s | details |
| #34 | ACCEPTED | 0.00 s | details |
| #35 | ACCEPTED | 0.00 s | details |
| #36 | ACCEPTED | 0.00 s | details |
| #37 | ACCEPTED | 0.00 s | details |
| #38 | ACCEPTED | 0.00 s | details |
| #39 | ACCEPTED | 0.00 s | details |
| #40 | ACCEPTED | 0.00 s | details |
| #41 | ACCEPTED | 0.00 s | details |
| #42 | ACCEPTED | 0.00 s | details |
| #43 | ACCEPTED | 0.00 s | details |
| #44 | ACCEPTED | 0.00 s | details |
| #45 | ACCEPTED | 0.00 s | details |
| #46 | ACCEPTED | 0.00 s | details |
| #47 | ACCEPTED | 0.00 s | details |
| #48 | ACCEPTED | 0.00 s | details |
| #49 | ACCEPTED | 0.00 s | details |
| #50 | ACCEPTED | 0.00 s | details |
| #51 | ACCEPTED | 0.00 s | details |
| #52 | ACCEPTED | 0.00 s | details |
| #53 | ACCEPTED | 0.00 s | details |
| #54 | ACCEPTED | 0.00 s | details |
| #55 | ACCEPTED | 0.00 s | details |
| #56 | ACCEPTED | 0.00 s | details |
| #57 | ACCEPTED | 0.00 s | details |
| #58 | ACCEPTED | 0.00 s | details |
| #59 | ACCEPTED | 0.00 s | details |
| #60 | ACCEPTED | 0.00 s | details |
| #61 | ACCEPTED | 0.00 s | details |
| #62 | ACCEPTED | 0.00 s | details |
| #63 | ACCEPTED | 0.00 s | details |
| #64 | ACCEPTED | 0.00 s | details |
| #65 | ACCEPTED | 0.00 s | details |
| #66 | ACCEPTED | 0.00 s | details |
| #67 | ACCEPTED | 0.00 s | details |
| #68 | ACCEPTED | 0.00 s | details |
| #69 | ACCEPTED | 0.00 s | details |
| #70 | ACCEPTED | 0.00 s | details |
| #71 | ACCEPTED | 0.00 s | details |
| #72 | ACCEPTED | 0.00 s | details |
| #73 | ACCEPTED | 0.00 s | details |
| #74 | ACCEPTED | 0.00 s | details |
| #75 | ACCEPTED | 0.00 s | details |
| #76 | ACCEPTED | 0.00 s | details |
| #77 | ACCEPTED | 0.00 s | details |
| #78 | ACCEPTED | 0.00 s | details |
| #79 | ACCEPTED | 0.00 s | details |
| #80 | ACCEPTED | 0.00 s | details |
Code
#![allow(unused)]
use std::cmp::max;
use std::collections::*;
use std::io;
fn take_tuple() -> (usize, usize) {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let mut it = input.trim().split_whitespace().map(|x| x.parse::<usize>().unwrap());
(it.next().unwrap(), it.next().unwrap())
}
const M: u64 = 998244353;
fn mul_mod(p: &[u64], q: &[u64], a: usize) -> Vec<u64> {
let mut r = vec![0u64; 2 * a - 1];
for (i, &pi) in p.iter().enumerate() {
if pi == 0 {
continue;
}
for (j, &qj) in q.iter().enumerate() {
r[i + j] = (r[i + j] + pi * qj) % M;
}
}
for d in (a..r.len()).rev() {
let c = r[d];
r[d - 1] = (r[d - 1] + c) % M;
r[d - a] = (r[d - a] + c) % M;
}
r.truncate(a);
r
}
fn main() {
let (a, b) = take_tuple();
let mut res = vec![0u64; a];
res[0] = 1;
let mut base = vec![0u64; a];
if a == 1 {
base[0] = 2;
} else {
base[1] = 1;
}
let mut e = b;
while e > 0 {
if e & 1 == 1 {
res = mul_mod(&res, &base, a);
}
base = mul_mod(&base, &base, a);
e >>= 1;
}
let ans = res.iter().fold(0, |s, &c| (s + c) % M);
println!("{ans}");
}
Test details
Test 1
Verdict: ACCEPTED
| input |
|---|
| 2 10 |
| correct output |
|---|
| 89 |
| user output |
|---|
| 89 |
Test 2
Verdict: ACCEPTED
| input |
|---|
| 2 6 |
| correct output |
|---|
| 13 |
| user output |
|---|
| 13 |
Test 3
Verdict: ACCEPTED
| input |
|---|
| 2 8 |
| correct output |
|---|
| 34 |
| user output |
|---|
| 34 |
Test 4
Verdict: ACCEPTED
| input |
|---|
| 2 68 |
| correct output |
|---|
| 977351119 |
| user output |
|---|
| 977351119 |
Test 5
Verdict: ACCEPTED
| input |
|---|
| 2 78 |
| correct output |
|---|
| 20929410 |
| user output |
|---|
| 20929410 |
Test 6
Verdict: ACCEPTED
| input |
|---|
| 2 76 |
| correct output |
|---|
| 878806424 |
| user output |
|---|
| 878806424 |
Test 7
Verdict: ACCEPTED
| input |
|---|
| 2 485 |
| correct output |
|---|
| 908660084 |
| user output |
|---|
| 908660084 |
Test 8
Verdict: ACCEPTED
| input |
|---|
| 2 519 |
| correct output |
|---|
| 838514871 |
| user output |
|---|
| 838514871 |
Test 9
Verdict: ACCEPTED
| input |
|---|
| 2 602 |
| correct output |
|---|
| 892152152 |
| user output |
|---|
| 892152152 |
Test 10
Verdict: ACCEPTED
| input |
|---|
| 2 165714 |
| correct output |
|---|
| 921473843 |
| user output |
|---|
| 921473843 |
Test 11
Verdict: ACCEPTED
| input |
|---|
| 3 6 |
| correct output |
|---|
| 6 |
| user output |
|---|
| 6 |
Test 12
Verdict: ACCEPTED
| input |
|---|
| 3 8 |
| correct output |
|---|
| 13 |
| user output |
|---|
| 13 |
Test 13
Verdict: ACCEPTED
| input |
|---|
| 2 7 |
| correct output |
|---|
| 21 |
| user output |
|---|
| 21 |
Test 14
Verdict: ACCEPTED
| input |
|---|
| 3 78 |
| correct output |
|---|
| 198155624 |
| user output |
|---|
| 198155624 |
Test 15
Verdict: ACCEPTED
| input |
|---|
| 2 76 |
| correct output |
|---|
| 878806424 |
| user output |
|---|
| 878806424 |
Test 16
Verdict: ACCEPTED
| input |
|---|
| 3 49 |
| correct output |
|---|
| 83316385 |
| user output |
|---|
| 83316385 |
Test 17
Verdict: ACCEPTED
| input |
|---|
| 2 519 |
| correct output |
|---|
| 838514871 |
| user output |
|---|
| 838514871 |
Test 18
Verdict: ACCEPTED
| input |
|---|
| 3 602 |
| correct output |
|---|
| 575081686 |
| user output |
|---|
| 575081686 |
Test 19
Verdict: ACCEPTED
| input |
|---|
| 2 166 |
| correct output |
|---|
| 833010588 |
| user output |
|---|
| 833010588 |
Test 20
Verdict: ACCEPTED
| input |
|---|
| 2 187222 |
| correct output |
|---|
| 206734446 |
| user output |
|---|
| 206734446 |
Test 21
Verdict: ACCEPTED
| input |
|---|
| 2 7 |
| correct output |
|---|
| 21 |
| user output |
|---|
| 21 |
Test 22
Verdict: ACCEPTED
| input |
|---|
| 5 8 |
| correct output |
|---|
| 5 |
| user output |
|---|
| 5 |
Test 23
Verdict: ACCEPTED
| input |
|---|
| 2 8 |
| correct output |
|---|
| 34 |
| user output |
|---|
| 34 |
Test 24
Verdict: ACCEPTED
| input |
|---|
| 5 49 |
| correct output |
|---|
| 486716 |
| user output |
|---|
| 486716 |
Test 25
Verdict: ACCEPTED
| input |
|---|
| 2 52 |
| correct output |
|---|
| 409340464 |
| user output |
|---|
| 409340464 |
Test 26
Verdict: ACCEPTED
| input |
|---|
| 5 61 |
| correct output |
|---|
| 14215310 |
| user output |
|---|
| 14215310 |
Test 27
Verdict: ACCEPTED
| input |
|---|
| 2 166 |
| correct output |
|---|
| 833010588 |
| user output |
|---|
| 833010588 |
Test 28
Verdict: ACCEPTED
| input |
|---|
| 2 188 |
| correct output |
|---|
| 914862760 |
| user output |
|---|
| 914862760 |
Test 29
Verdict: ACCEPTED
| input |
|---|
| 5 611 |
| correct output |
|---|
| 386811672 |
| user output |
|---|
| 386811672 |
Test 30
Verdict: ACCEPTED
| input |
|---|
| 4 672099 |
| correct output |
|---|
| 5039638 |
| user output |
|---|
| 5039638 |
Test 31
Verdict: ACCEPTED
| input |
|---|
| 77 10 |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 32
Verdict: ACCEPTED
| input |
|---|
| 76 1 |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 33
Verdict: ACCEPTED
| input |
|---|
| 80 7 |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 34
Verdict: ACCEPTED
| input |
|---|
| 72 56 |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 35
Verdict: ACCEPTED
| input |
|---|
| 57 97 |
| correct output |
|---|
| 42 |
| user output |
|---|
| 42 |
Test 36
Verdict: ACCEPTED
| input |
|---|
| 54 58 |
| correct output |
|---|
| 6 |
| user output |
|---|
| 6 |
Test 37
Verdict: ACCEPTED
| input |
|---|
| 50 639 |
| correct output |
|---|
| 373574336 |
| user output |
|---|
| 373574336 |
Test 38
Verdict: ACCEPTED
| input |
|---|
| 58 195 |
| correct output |
|---|
| 5403 |
| user output |
|---|
| 5403 |
Test 39
Verdict: ACCEPTED
| input |
|---|
| 61 694 |
| correct output |
|---|
| 605984493 |
| user output |
|---|
| 605984493 |
Test 40
Verdict: ACCEPTED
| input |
|---|
| 9 616206422053543989 |
| correct output |
|---|
| 952862778 |
| user output |
|---|
| 952862778 |
Test 41
Verdict: ACCEPTED
| input |
|---|
| 6 169825965437345849 |
| correct output |
|---|
| 513277084 |
| user output |
|---|
| 513277084 |
Test 42
Verdict: ACCEPTED
| input |
|---|
| 5 191867851255868863 |
| correct output |
|---|
| 33742481 |
| user output |
|---|
| 33742481 |
Test 43
Verdict: ACCEPTED
| input |
|---|
| 9 625431978270398522 |
| correct output |
|---|
| 737838270 |
| user output |
|---|
| 737838270 |
Test 44
Verdict: ACCEPTED
| input |
|---|
| 8 688779226095035965 |
| correct output |
|---|
| 162344930 |
| user output |
|---|
| 162344930 |
Test 45
Verdict: ACCEPTED
| input |
|---|
| 10 802140689263714569 |
| correct output |
|---|
| 90271065 |
| user output |
|---|
| 90271065 |
Test 46
Verdict: ACCEPTED
| input |
|---|
| 6 326105735534681902 |
| correct output |
|---|
| 815511427 |
| user output |
|---|
| 815511427 |
Test 47
Verdict: ACCEPTED
| input |
|---|
| 6 714378023239269070 |
| correct output |
|---|
| 974264931 |
| user output |
|---|
| 974264931 |
Test 48
Verdict: ACCEPTED
| input |
|---|
| 8 389060406667759103 |
| correct output |
|---|
| 997632165 |
| user output |
|---|
| 997632165 |
Test 49
Verdict: ACCEPTED
| input |
|---|
| 5 752611790930241374 |
| correct output |
|---|
| 663785595 |
| user output |
|---|
| 663785595 |
Test 50
Verdict: ACCEPTED
| input |
|---|
| 9 616206422053543989 |
| correct output |
|---|
| 952862778 |
| user output |
|---|
| 952862778 |
Test 51
Verdict: ACCEPTED
| input |
|---|
| 9 616206422053543989 |
| correct output |
|---|
| 952862778 |
| user output |
|---|
| 952862778 |
Test 52
Verdict: ACCEPTED
| input |
|---|
| 10 292432805466778024 |
| correct output |
|---|
| 54188787 |
| user output |
|---|
| 54188787 |
Test 53
Verdict: ACCEPTED
| input |
|---|
| 12 877206118126603157 |
| correct output |
|---|
| 50978391 |
| user output |
|---|
| 50978391 |
Test 54
Verdict: ACCEPTED
| input |
|---|
| 15 106209626593822568 |
| correct output |
|---|
| 26611817 |
| user output |
|---|
| 26611817 |
Test 55
Verdict: ACCEPTED
| input |
|---|
| 20 599479100988098599 |
| correct output |
|---|
| 119658586 |
| user output |
|---|
| 119658586 |
Test 56
Verdict: ACCEPTED
| input |
|---|
| 19 751085324932436268 |
| correct output |
|---|
| 362164431 |
| user output |
|---|
| 362164431 |
Test 57
Verdict: ACCEPTED
| input |
|---|
| 13 653792349017119940 |
| correct output |
|---|
| 727329363 |
| user output |
|---|
| 727329363 |
Test 58
Verdict: ACCEPTED
| input |
|---|
| 14 922927469528725341 |
| correct output |
|---|
| 702679243 |
| user output |
|---|
| 702679243 |
Test 59
Verdict: ACCEPTED
| input |
|---|
| 18 278820978471154000 |
| correct output |
|---|
| 447470474 |
| user output |
|---|
| 447470474 |
Test 60
Verdict: ACCEPTED
| input |
|---|
| 19 595145428494262541 |
| correct output |
|---|
| 321383191 |
| user output |
|---|
| 321383191 |
Test 61
Verdict: ACCEPTED
| input |
|---|
| 16 733419934325111819 |
| correct output |
|---|
| 603915854 |
| user output |
|---|
| 603915854 |
Test 62
Verdict: ACCEPTED
| input |
|---|
| 42 977794035917013551 |
| correct output |
|---|
| 535001165 |
| user output |
|---|
| 535001165 |
Test 63
Verdict: ACCEPTED
| input |
|---|
| 46 107297864267805308 |
| correct output |
|---|
| 557129508 |
| user output |
|---|
| 557129508 |
Test 64
Verdict: ACCEPTED
| input |
|---|
| 47 423649320883482177 |
| correct output |
|---|
| 894439428 |
| user output |
|---|
| 894439428 |
Test 65
Verdict: ACCEPTED
| input |
|---|
| 35 923635615021083310 |
| correct output |
|---|
| 306200203 |
| user output |
|---|
| 306200203 |
Test 66
Verdict: ACCEPTED
| input |
|---|
| 27 119042622192684556 |
| correct output |
|---|
| 95698341 |
| user output |
|---|
| 95698341 |
Test 67
Verdict: ACCEPTED
| input |
|---|
| 50 394425873219136058 |
| correct output |
|---|
| 461849248 |
| user output |
|---|
| 461849248 |
Test 68
Verdict: ACCEPTED
| input |
|---|
| 27 702344952743354850 |
| correct output |
|---|
| 361328763 |
| user output |
|---|
| 361328763 |
Test 69
Verdict: ACCEPTED
| input |
|---|
| 34 148052957467783205 |
| correct output |
|---|
| 883611228 |
| user output |
|---|
| 883611228 |
Test 70
Verdict: ACCEPTED
| input |
|---|
| 49 120057477600708020 |
| correct output |
|---|
| 411727310 |
| user output |
|---|
| 411727310 |
Test 71
Verdict: ACCEPTED
| input |
|---|
| 77 985532091144101696 |
| correct output |
|---|
| 533259046 |
| user output |
|---|
| 533259046 |
Test 72
Verdict: ACCEPTED
| input |
|---|
| 76 62568531781086688 |
| correct output |
|---|
| 111230040 |
| user output |
|---|
| 111230040 |
Test 73
Verdict: ACCEPTED
| input |
|---|
| 80 638842883372078079 |
| correct output |
|---|
| 843571033 |
| user output |
|---|
| 843571033 |
Test 74
Verdict: ACCEPTED
| input |
|---|
| 72 568029317340376926 |
| correct output |
|---|
| 760917479 |
| user output |
|---|
| 760917479 |
Test 75
Verdict: ACCEPTED
| input |
|---|
| 57 993363883840818838 |
| correct output |
|---|
| 125996687 |
| user output |
|---|
| 125996687 |
Test 76
Verdict: ACCEPTED
| input |
|---|
| 54 587462523883449402 |
| correct output |
|---|
| 707247678 |
| user output |
|---|
| 707247678 |
Test 77
Verdict: ACCEPTED
| input |
|---|
| 50 654341799647462242 |
| correct output |
|---|
| 823275735 |
| user output |
|---|
| 823275735 |
Test 78
Verdict: ACCEPTED
| input |
|---|
| 58 198843859011456415 |
| correct output |
|---|
| 392227014 |
| user output |
|---|
| 392227014 |
Test 79
Verdict: ACCEPTED
| input |
|---|
| 61 710225245014179861 |
| correct output |
|---|
| 352309063 |
| user output |
|---|
| 352309063 |
Test 80
Verdict: ACCEPTED
| input |
|---|
| 81 435847411137743327 |
| correct output |
|---|
| 639314946 |
| user output |
|---|
| 639314946 |
