【洛谷 p3390】模板-矩阵快速幂（数论）
题目：给定n*n的矩阵A，求A^k。
解法：利用矩阵乘法的定义和快速幂解答。注意用负数，但是数据太弱没有卡到我......（P.S.不要在 typedef long long LL; 前使用 LL......━━(￣ー￣*|||━━）
P.S.在multi函数里，若将所有相乘的和先加起来不会爆 long long ，那就最后再模会快不少。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 typedef long long LL; 7 8 const int N=110,D=1010; 9 const LL K=(LL)1e12+10,mod=(LL)1e9+7; 10 int n; 11 struct mat{LL s[N][N];}a,b,c,d,e,f; 12 13 mat multi(mat c,mat d) 14 { 15 for (int i=1;i<=n;i++) 16 for (int j=1;j<=n;j++) 17 { 18 e.s[i][j]=0; 19 for (int k=1;k<=n;k++) 20 e.s[i][j]=(e.s[i][j]+mod+(c.s[i][k]*d.s[k][j])%mod+mod)%mod; 21 } 22 return e; 23 } 24 mat qpow(mat a,LL k) 25 { 26 b=a; k--; 27 while (k>0) 28 { 29 if (k&1) b=multi(b,a); 30 a=multi(a,a); 31 k>>=1; 32 } 33 return b; 34 } 35 int main() 36 { 37 LL k; 38 scanf("%d%lld",&n,&k); 39 for (int i=1;i<=n;i++) 40 for (int j=1;j<=n;j++) 41 scanf("%lld",&f.s[i][j]); 42 f=qpow(f,k); 43 for (int i=1;i<=n;i++) 44 { 45 for (int j=1;j<=n;j++) 46 printf("%lld ",f.s[i][j]); 47 printf(" "); 48 } 49 return 0; 50 }