非常普通的矩阵快速幂...
但是我
第一次写忘了矩阵不能交换律...
第一二次提交RE直到看到题解才发现这道题不能用递归快速幂...
第三次提交成了c编译错误...
第四次提交WA发现写循环快速幂的时候少清零了一个f...
所以提交了五次才终于对了,什么垃圾的代码能力...通过率杀手...
希望下次能捡起我的脑子....
代码很简单 如下
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int maxn=110; 9 const double eps=1e-8; 10 int n,m; 11 struct mat{ 12 int e[maxn][maxn]; 13 }; 14 mat pro(mat x,mat y){ 15 mat z; 16 for(int i=1;i<=n;i++){ 17 for(int j=1;j<=n;j++){ 18 z.e[i][j]=0; 19 for(int k=1;k<=n;k++){ 20 z.e[i][j]+=x.e[i][k]*y.e[k][j]; 21 } 22 } 23 }return z; 24 } 25 mat pow(mat x,int k){ 26 mat z; 27 bool f=1; 28 while(k>0){ 29 if(k%2!=0){ 30 if(f){ 31 z=x; 32 f=0; 33 }else{ 34 z=pro(x,z); 35 } 36 }k/=2; 37 x=pro(x,x); 38 } 39 return z; 40 } 41 int main(){ 42 int k; 43 scanf("%d%d%d",&n,&m,&k); 44 int x,z,w; 45 z=k/m; w=k%m; mat c; 46 for(int i=1;i<=n;i++){ 47 for(int j=1;j<=n;j++){ 48 c.e[i][j]=0; 49 } 50 } 51 mat a=c; mat d=c; 52 for(int i=1;i<=m;i++){ 53 mat b=c; 54 if(i==1){ 55 for(int j=1;j<=n;j++){ 56 scanf("%d",&x); 57 a.e[j][x]=1; 58 } 59 if(w>=1){ 60 d=a; 61 } 62 continue; 63 } 64 for(int j=1;j<=n;j++){ 65 scanf("%d",&x); 66 b.e[j][x]=1; 67 } 68 a=pro(b,a); 69 if(i<=w){ 70 d=a; 71 } 72 } 73 if(z==0){ 74 a=d; 75 }else if(w==0){ 76 c=a; 77 a=pow(c,z); 78 }else{ 79 c=a; 80 a=pro(d,pow(c,z)); 81 } 82 for(int i=1;i<=n;i++){ 83 for(int j=1;j<=n;j++){ 84 if(a.e[i][j]!=0){ 85 printf("%d ",j); 86 break; 87 } 88 } 89 } 90 cout<<endl; 91 return 0; 92 }