Fibonacci towers

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;

const int Q = 998244353;

const int O = 101;

void mul(ll *m, ll *n) {
	ll d[O*O];
	for (int y=0; y < O; ++y) {
		for (int x=0; x < O; ++x) {
			int c = y*O+x;
			d[c] = 0;
			for (int i=0; i < O; ++i) {
				d[c] += m[y*O+i]*n[i*O+x];
				d[c] %= Q;
			}
		}
	}
	copy(d,d+O*O,m);
}
 
void mpow(ll *m, ll p) {
	ll d[O*O];
	fill(d,d+O*O,0);
	for (int i=0; i < O; ++i) d[i*O+i] = 1;
	while (p) {
		if (p%2) mul(d,m);
		mul(m,m);
		p /= 2;
	}
	copy(d,d+O*O,m);
}

ll FF[O];

ll A[O*O];

int main() {
  ll a, b;
  cin >> a >> b;
  FF[0] = FF[1] = 1;
  for (int i = 2; i < O; ++i) {
    FF[i] = FF[i-1] + (i-a < 0 ? 0 : FF[i-a]);
    FF[i] %= Q;
  }
  if (a >= b || b < O) {
    cout << FF[b] << '\n';
    return 0;
  }
  for (int i = 0; i < O-1; ++i) {
    A[i*O + (i+1)] = 1;
  }
  A[O*O-1] = 1;
  A[O*O-a] = 1;
  mpow(A,b-O+1);
  ll ans = 0;
  for (int i = 0; i < O; ++i) {
    ans += A[O*(O-1)+i] * FF[i] % Q;
  }
  cout << ans % Q << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED

Test 66

Verdict: ACCEPTED

Test 67

Verdict: ACCEPTED

Test 68

Verdict: ACCEPTED

Test 69

Verdict: ACCEPTED

Test 70

Verdict: ACCEPTED

Test 71

Verdict: ACCEPTED

Test 72

Verdict: ACCEPTED

Test 73

Verdict: ACCEPTED

Test 74

Verdict: ACCEPTED

Test 75

Verdict: ACCEPTED

Test 76

Verdict: ACCEPTED

Test 77

Verdict: ACCEPTED

Test 78

Verdict: ACCEPTED

Test 79

Verdict: ACCEPTED

Test 80

Verdict: ACCEPTED