Training little cats poj-3735
题目大意：给你n个数，k个操作，将所有操作重复m次。
注释：三种操作，将第i个盒子+1，交换两个盒子中的个数，将一个盒子清空。$1\le m \le 10^9$ , $1\le n , k \le 100$。
想法：定义开始是的矩阵是n+1行，1列，除了最底下的数是1剩下全是0。然后加法操作就是讲操作答案矩阵的对应位置+1，交换操作就是暴力交换操作答案矩阵的两行，清空操作是将操作答案矩阵的对应行清零。
至于最后的将所有操作重复，将单次操作答案矩阵快速幂即可。
最后，附上丑陋的代码... ...
#include#include #include #include #define N 110 using namespace std;struct Matr{ int x,y; int a[N][N]; Matr(){memset(a,0,sizeof a);} Matr operator *(const Matr &z) { Matr re; re.x=x; re.y=z.y; for(int i=1;i<=x;i++) { for(int j=1;j<=z.y;j++) { for(int k=1;k<=y;k++) { re.a[i][j]=(re.a[i][j]+a[i][k]*z.a[k][j]); } } } return re; }};int n;Matr quick_power(Matr &a,int k){ Matr x; x.x=x.y=n+1; for(int i=1;i<=n+1;i++) { x.a[i][i]=1; } Matr y=a; while(k) { if(k&1) x=x*y; y=y*y; k>>=1; } return x;}int main(){ while(1) { int k,m; scanf("%d%d%d",&n,&m,&k); if(!n&&!m&&!k) return 0; if(m==0) { for(int i=1;i<=n;i++) { printf("0 "); } puts(""); continue; } Matr x; x.x=x.y=n+1; for(int i=1;i<=n+1;i++) { x.a[i][i]=1; } Matr ans=x; // cout << k << "Fuck" << endl; for(int i=1;i<=k;i++) { int number; char s[20]; scanf("%s",s+1); if(s[1]=='g') { scanf("%d",&number); Matr a=x; a.a[number][n+1]=1; ans=ans*a; // cout << i << endl; } if(s[1]=='e') { scanf("%d",&number); for(int j=1;j<=n+1;j++) { ans.a[number][j]=0; } // ans=ans*a; } if(s[1]=='s') { int p,q; scanf("%d%d",&p,&q); // Matr a=x; for(int j=1;j<=n+1;j++) { int middle=ans.a[q][j]; ans.a[q][j]=ans.a[p][j]; ans.a[p][j]=middle; // swap(ans.a[p][j],ans.a[q][j]); } // ans=ans*a; } // puts("begin"); // for(int j=1;j<=n+1;j++) // { // for(int r=1;r<=n+1;r++) // { // cout << ans.a[j][r] << " " ; // } // puts(""); // } // puts("end"); } // if(m==0) // { // for(int i=1;i<=n;i++) // { // printf("0 "); // } // puts(""); // } if(m!=1) ans=quick_power(ans,m); Matr ori; ori.x=n+1; ori.y=1; ori.a[n+1][1]=1; ans=ans*ori; for(int i=1;i<=n;i++) { printf("%d ",ans.a[i][1]); } puts(""); // return 0; }}// int main()// {// Matr a,b;// a.x=a.y=b.x=b.y=3;// for(int i=1;i<=3;i++)// {// a.a[i][i]=1;// }// a.a[2][3]=1;// for(int i=1;i<=3;i++)// {// swap(a.a[1][i],a.a[2][i]);// }// for(int i=1;i<=3;i++)// {// for(int j=1;j<=3;j++)// {// cout << a.a[i][j] << " " ;// }// cout << endl ;// }// return 0;// }
小结：矩阵好写难调，用处不广泛，但是一些题有奇效(JLOI2018D2T2qwq)