# [模板] 矩阵加速递推运算

## Fibonacci 数列

$$f_0 = 0，f_1 = 1$$

$$f_i = f_{i-1} +f_{n+2}$$

## 矩阵加速线性递推

$$A = \left[ \begin{matrix} 0 & 1 \\ 1 & 1 \\ \end{matrix} \right]$$

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 10 + 10;

int n, MOD;

struct Matrix{
int n, m;
int data[MAXN][MAXN];

Matrix(int _n, int _m){
n = _n;
m = _m;
memset(data, 0, sizeof(data));
}

Matrix operator + (Matrix a){
Matrix ans(n, m);
for(register int i=1; i<=n; i++){
for(register int j=1; j<=m; j++){
ans.data[i][j] = (data[i][j] + a.data[i][j]) % MOD;
}
}

return ans;
}

Matrix operator * (Matrix a){
Matrix ans(n, a.m);

for(register int i=1; i<=n; i++){
for(register int j=1; j<=a.m; j++){
long long t = 0;

for(register int k=1; k<=m; k++){
t = (t + ((long long)data[i][k] * a.data[k][j]) % MOD) % MOD;
}

ans.data[i][j] = t;
}
}

return ans;
}
};

Matrix pow(Matrix a, int n){
Matrix ans(a.n, a.n), tmp(a.n, a.n);

for(register int i=1; i<=a.n; i++)
ans.data[i][i] = 1;

memcpy(tmp.data, a.data, sizeof(tmp.data));

while(n){
if(n & 1)
ans = ans * tmp;

n >>= 1;
tmp = tmp * tmp;
}

return ans;
}

int main(){
scanf("%d%d", &n, &MOD);

Matrix start(1, 2);
start.data[1][1] = 0;
start.data[1][2] = 1;

Matrix transform(2, 2);
transform.data[1][1] = 0;
transform.data[1][2] = 1;
transform.data[2][1] = 1;
transform.data[2][2] = 1;

Matrix ans = start * pow(transform, n);

printf("%d", ans.data[1][1]);
return 0;
}