后面的可以由前面递推而来所以直接递归就行了
#include <cstdio> #include <cstdlib> #include <iostream> using namespace std; #define ll long long #define re register #define pb push_back #define fi first #define se second const int N=1e6+10; const int mod=1e9+7; void read(int &a) { a=0;int d=1;char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } int n,m,k; struct note{int a[35][35];}ans,a; note mul(note x,note y) { note c; for(re int i=1;i<=n;i++) for(re int j=1;j<=n;j++) { c.a[i][j]=0; for(re int l=1;l<=n;l++) c.a[i][j]=(c.a[i][j]+x.a[i][l]*y.a[l][j]%m)%m;///啥也别问，只要加了在这里加了1ll*就会T，不知道为啥 } return c; } note add(note x,note y) { note c; for(re int i=1;i<=n;i++) for(re int j=1;j<=n;j++) c.a[i][j]=(x.a[i][j]+y.a[i][j])%m; return c; } note quickmod(note x,int y) { note res,base=x; for(re int i=1;i<=n;i++) for(re int j=1;j<=n;j++) if(i==j) res.a[i][j]=1; else res.a[i][j]=0; while(y) { if(y&1) res=mul(res,base); base=mul(base,base); y>>=1; } return res; } note dfs(int x) { if(x==1) return a; note res=dfs(x/2),c; if(x&1) { c=quickmod(a,x/2+1); res=add(res,mul(c,res)); res=add(res,c); return res; } c=quickmod(a,x/2); res=add(res,mul(c,res)); return res; } int main() { read(n),read(k),read(m); for(re int i=1;i<=n;i++) { for(re int j=1;j<=n;j++) { read(a.a[i][j]); a.a[i][j]%=m; if(i==j) ans.a[i][j]=1; else ans.a[i][j]=0; } } note res=dfs(k); for(re int i=1;i<=n;i++) { for(re int j=1;j<=n;j++) printf("%d ",res.a[i][j]%m); putchar(' '); } return 0; }