poj3233
年幼无知的代码:
#include<iostream> // #include<cstdio> //#include<bits/stdc++.h> using namespace std; typedef long long LL; #define INF 1e8 #define inf 0x3f3f3f3f const int mod = 10000; int n,k,m; struct Mat { int m[35][35]; };//存储结构体 Mat s,A,a00,a01,a10,a11; Mat Mul(Mat x,Mat y)//矩阵x*y { Mat c; for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ c.m[i][j] = 0; } } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ for(int k=1;k<=n;++k){ c.m[i][j] += x.m[i][k]*y.m[k][j]%m; } } } return c; } Mat operate(Mat x,Mat y){ Mat c; for(int i = 1; i <= n ;i++) for(int j = 1; j <= n; j++) c.m[i][j] = (x.m[i][j]+y.m[i][j])%m; return c; } void Muls(){ Mat temp00,temp01,temp10,temp11; temp00 = operate(Mul(a00,a00),Mul(a10,a01)); temp01 = operate(Mul(a00,a01),Mul(a01,a11)); temp10 = operate(Mul(a10,a00),Mul(a11,a10)); temp11 = operate(Mul(a10,a01),Mul(a11,a11)); a00 = temp00;a01 = temp01;a10 = temp10;a11 = temp11; } void pow(int y)//矩阵快速幂 { Mat x,a = A; while(y){ if(y&1) { x = s; s = operate(Mul(s,a00),Mul(A,a10)); A = operate(Mul(x,a01),Mul(A,a11)); } Muls(); y >>= 1; } } int main(){ cin>>n>>k>>m; for(int i = 1 ; i <= n; ++i){ for(int j = 1 ; j <= n ;++j){ cin>>A.m[i][j]; s.m[i][j] = a10.m[i][j]=a11.m[i][j] = A.m[i][j]; if(i==j) a00.m[i][j] = 1; else a00.m[i][j] = 0; a01.m[i][j] = 0; } } pow(k-1); for(int i = 1 ; i <= n; i++) { for(int j = 1 ; j < n ;j++) cout<<s.m[i][j]%m<<" "; cout<<s.m[i][n]%m<<endl; } }