@[ZCDHJ](/space/show?uid=24878) 根据dp方程$f[i][j]=f[i-1][j-1]+f[i-1][j+1]$构造一个8*8的转移矩阵再快速幂
by 香风智乃 @ 2018-08-23 17:38:27
我好像挖坟了qwq
by 香风智乃 @ 2018-08-23 17:39:20
这道题可以的，首先先套矩阵快速幂的模板。
```cpp
struct mt{
long long a[8][8],n,m;
mt(){}
mt(int _n,int _m){
n = _n;
m = _m;
memset(a,0,sizeof(a));
}
mt operator*(mt &x){
mt t = mt(n, x.m);
for(int i = 0; i < n; i++){
for(int j = 0; j < x.m; j++){
for(int k = 0; k < m; k++){
t.a[i][j] += a[i][k] * x.a[k][j];
t.a[i][j] /= mod;
}
}
}
return t;
}
mt operator^(long long x){
mt t = *this,res = mt(n,n);
for(int i = 0; i < n; i++){
res.a[i][i] = 1;
}
while(x){
if(x % 2 ==1){
res = res * t;
}
x /= 2;
t = t * t;
}
return res;
}
};
```
by 雨绪 @ 2019-03-25 15:28:31
一个连通图的n次方中[i][j]即为从i到j走n步的方案
by lili_flyingcutter @ 2020-09-24 23:10:31
rt @[iodwad](/user/24878)
by bigmurmur @ 2022-03-09 17:35:34