? #include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}const int N=9; ll n; struct mat {ll a[N][N]; }; mat mat_mul(mat x,mat y) {mat res; mem(res.a,0); for(int i=0;i<N;i++)for(int j=0;j<N;j++) for(int k=0;k<N;k++)res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%mod;return res; } mat mat_pow(ll n) {mat c,res;mem(c.a,0);//initc.a[0][3]=c.a[0][6]=1;c.a[1][0]=c.a[1][6]=1;c.a[2][0]=c.a[2][3]=c.a[2][6]=1;c.a[3][1]=c.a[3][4]=1;c.a[4][1]=c.a[4][7]=1;c.a[5][4]=c.a[5][7]=1;c.a[6][2]=c.a[6][5]=c.a[6][8]=1;c.a[7][2]=c.a[7][8]=1;c.a[8][2]=c.a[8][5]=1;mem(res.a,0);for(int i=0;i<N;i++) res.a[i][i]=1; while(n){if(n&1) res=mat_mul(res,c); c=mat_mul(c,c); n>>=1;}//resreturn res; }

?

總結(jié)

以上是生活随笔為你收集整理的矩阵快速幂模板~的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。