Matrix Exponentiation
O(k³ log e)Raise a k×k matrix to a huge power by binary exponentiation. Turns any fixed linear recurrence (Fibonacci, path counting, linear DP with tiny state) into an O(k³ log n) computation, so n up to 10^18 is fine.
// use it on
CSES: Fibonacci Numbers ↗
F(n) for n up to 10^18: power the 2×2 matrix [[1,1],[1,0]] to the n-th and read off the corner.
// the code
const long long MOD = 998244353;
using Mat = vector<vector<long long>>;
Mat mul(const Mat& A, const Mat& B) {
int n = A.size(), m = B[0].size(), k = B.size();
Mat C(n, vector<long long>(m, 0));
for (int i = 0; i < n; i++)
for (int t = 0; t < k; t++) {
if (A[i][t] == 0) continue;
for (int j = 0; j < m; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Mat mat_pow(Mat A, long long e) {
int n = A.size();
Mat R(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) R[i][i] = 1;
for (; e > 0; e >>= 1, A = mul(A, A))
if (e & 1) R = mul(R, A);
return R;
}
// Fibonacci: mat_pow({{1,1},{1,0}}, n)[0][1] == F(n)