注意: 矩阵快速幂把一个二维数组(方阵)放在了struct中,快速幂只适用于方阵size较小的情况,如果size过大的话,main中的栈会溢出,并且由于一次矩阵乘法复杂度是O(n3),很容易超时。
对于一些特别的题,如循环矩阵的话,可以只保留第一行这样就会快很多
例题:https://ac.nowcoder.com/acm/contest/7079/D
题解:https://ac.nowcoder.com/discuss/492088?type=101&order=time&pos=&page=1&channel=666&source_id=search_acm_post
### 快速幂:
###blog:https://blog.csdn.net/qq_44266648/article/details/97500679
代码块 int poww(ll a, ll b, ll mod) { ll ans = 1; ll base = a % mod; while (b) { if (b & 1 != 0) ans = ans * base % mod; b = b >> 1; base = base * base % mod; } return ans; }
矩阵快速幂:
blog:https://blog.csdn.net/qq_41021816/article/details/82760216
代码块 const int N=9; struct Matrix{///矩阵结构体 ll matrix[N][N]; }; const int mod = 1e9 + 7; void init(Matrix &res)///初始化为单位矩阵 { memset(res.matrix,0,sizeof(res.matrix)); for(int i=0;i<N;i++) res.matrix[i][i]=1; } Matrix multiplicative(Matrix a,Matrix b)///矩阵乘法 { Matrix res; memset(res.matrix,0,sizeof(res.matrix)); for(int i = 0 ; i < N ; i++){ for(int j = 0 ; j < N ; j++){ for(int k = 0 ; k < N ; k++){ res.matrix[i][j] += a.matrix[i][k]*b.matrix[k][j]; res.matrix[i][j] %= mod; } } } return res; } Matrix Pow(Matrix mx,ll m)///矩阵快速幂 { Matrix res,base=mx; init(res); while(m) { if(m&1) res=multiplicative(res,base); base=multiplicative(base,base); m>>=1; } return res; }