Fibonacci towers

#include <iostream>
#include <cstring>
#include <cassert>

using namespace std;

const int N = 1e2 + 5;
const int MOD = 998244353;

void add(int &a, int b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
}

int mul(int a, int b) {
  return 1LL * a * b % MOD;
}

struct matrix {
  int n, m;
  int mat[N][N];

  matrix() {
    memset(mat, 0, sizeof(mat));
  }

  matrix(int _n, int _m) {
    n = _n;
    m = _m;
    memset(mat, 0, sizeof(mat));
  }

  matrix operator * (const matrix &o) {
    matrix ans(this->n, o.m);
    assert(this->m == o.n);
    for (int i = 0; i < this->n; i++) {
      for (int j = 0; j < o.m; j++) {
        for (int k = 0; k < this->m; k++) {
          add(ans.mat[i][j], mul(this->mat[i][k], o.mat[k][j]));
        }
      }
    }
    return ans;
  }

  void operator *= (const matrix &o) {
    *this = *this * o;
  }

  matrix operator ^ (long long k) {
    assert(this->n == this->m);
    matrix res(this->n, this->n);
    for (int i = 0; i < this->n; i++) {
      res.mat[i][i] = 1;
    }
    matrix t = *this;
    for (; k > 0; t *= t, k >>= 1) {
      if (k & 1) {
        res *= t;
      }
    }
    return res;
  }

  void operator ^= (long long k) {
    *this = *this ^ k;
  }
};

int a;
long long b;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> a >> b;
  matrix f(1, a + 1);
  f.mat[0][0] = 1;
  for (int i = 1; i <= a; i++) {
    add(f.mat[0][i], f.mat[0][i - 1]);
  }
  add(f.mat[0][a], f.mat[0][0]);
  if (a >= b) {
    cout << f.mat[0][b] << '\n';
    return 0;
  }
  matrix t(a + 1, a + 1);
  for (int i = 0; i < a; i++) {
    t.mat[i + 1][i] = 1;
  }
  t.mat[1][a] = 1;
  t.mat[a][a] = 1;
  t ^= b - a;
  f *= t;
  cout << f.mat[0][a] << '\n';
  return 0;
}

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