| Task: | Fibonacci towers |
| Sender: | aalto26km_036 |
| Submission time: | 2026-11-16 16:58:42 +0200 |
| Language: | C++ (C++23) |
| 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.01 s | details |
| #38 | ACCEPTED | 0.01 s | details |
| #39 | ACCEPTED | 0.01 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.01 s | details |
| #55 | ACCEPTED | 0.01 s | details |
| #56 | ACCEPTED | 0.01 s | details |
| #57 | ACCEPTED | 0.00 s | details |
| #58 | ACCEPTED | 0.01 s | details |
| #59 | ACCEPTED | 0.01 s | details |
| #60 | ACCEPTED | 0.01 s | details |
| #61 | ACCEPTED | 0.01 s | details |
| #62 | ACCEPTED | 0.02 s | details |
| #63 | ACCEPTED | 0.02 s | details |
| #64 | ACCEPTED | 0.02 s | details |
| #65 | ACCEPTED | 0.01 s | details |
| #66 | ACCEPTED | 0.01 s | details |
| #67 | ACCEPTED | 0.02 s | details |
| #68 | ACCEPTED | 0.01 s | details |
| #69 | ACCEPTED | 0.01 s | details |
| #70 | ACCEPTED | 0.02 s | details |
| #71 | ACCEPTED | 0.07 s | details |
| #72 | ACCEPTED | 0.07 s | details |
| #73 | ACCEPTED | 0.08 s | details |
| #74 | ACCEPTED | 0.06 s | details |
| #75 | ACCEPTED | 0.03 s | details |
| #76 | ACCEPTED | 0.03 s | details |
| #77 | ACCEPTED | 0.02 s | details |
| #78 | ACCEPTED | 0.03 s | details |
| #79 | ACCEPTED | 0.04 s | details |
| #80 | ACCEPTED | 0.08 s | details |
Code
// #ifdef ONLINE_JUDGE
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #endif
#include "bits/stdc++.h"
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fill(arr,val) memset(arr,val,sizeof(arr))
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define dq deque<int>
#define nend '\n'
using namespace std;
const ll inf = 1e18;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};
const int MOD = 1e9 + 7;
const ll hashi = 2e9 + 11;
void init_code() {
fast;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
const ll P=998244353;
int a;
ll b;
typedef vector<vector<ll>> mat;
mat mul(const mat& A, const mat& B) {
int n=A.size();
mat C(n, vector<ll>(n,0));
FOR(i,0,n-1) FOR(k,0,n-1) if (A[i][k]) {
ll x=A[i][k];
FOR(j,0,n-1) C[i][j]=(C[i][j]+x*B[k][j])%P;
}
return C;
}
/// f(h) = amount of different towers at height h, with top block is 1 or a
/// f(h) = f(h-1) + f(h-a), f(0..a-1) = 1
/// b 1e18 [f(h), f(h-1), ..., f(h-a+1)]
void solve() {
cin >> a >> b;
if (b<a) {
cout << 1 << nend; return;
}
mat matrix(a, vector<ll>(a,0));
matrix[0][0]=1; matrix[0][a-1] = 1;
FOR(i,1,a-1) matrix[i][i-1] = 1;
mat R(a, vector<ll>(a,0));
FOR(i,0,a-1) R[i][i] = 1;
ll e=b-(a-1);
while (e) {
if (e&1) R=mul(R,matrix);
matrix=mul(matrix, matrix);
e >>=1;
}
ll ans=0;
FOR(j,0,a-1) ans = (ans + R[0][j])%P;
cout << ans << nend;
}
int main() {
init_code();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
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 |
