题意：
给一个长度为n的数列，，初始化为0，有3种操作：1）将某个元素增加1;2）将某个元素置0；3)交换两个元素。现在给出包含k个操作的一组操作，求m组操作后数列的状态。
分析：
找出初始矩阵A和转移矩阵T后就可以用快速幂计算了。
代码：
//poj 3735//sep9#include <iostream>using namespace std;typedef long long LL;const int maxN=128;int n,m,k;struct Matrix{LL a[maxN][maxN];void init(){memset(a,0,sizeof(a));for(int i=0;i<=n;++i)a[i][i]=1;}}A,T;Matrix operator *(Matrix x,Matrix y){Matrix tmp;memset(tmp.a,0,sizeof(tmp.a));for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)if(x.a[i][j])for(int k=0;k<=n;++k)tmp.a[i][k]+=x.a[i][j]*y.a[j][k];return tmp;}Matrix exp(Matrix x,int n){Matrix tmp;tmp.init();while(n){if(n&1) tmp=tmp*x;x=x*x;n>>=1;}return tmp;}int main(){while(scanf("%d%d%d",&n,&m,&k)==3){if(!n&&!m&&!k) break;memset(A.a,0,sizeof(A.a));A.a[0][0]=1;T.init();while(k–){char op[8];int x,y;scanf("%s",op);if(op[0]=='g'){scanf("%d",&x);++T.a[0][x];}else if(op[0]=='e'){scanf("%d",&x);for(int i=0;i<=n;++i)T.a[i][x]=0;}else{scanf("%d%d",&x,&y);for(int i=0;i<=n;++i)swap(T.a[i][x],T.a[i][y]);}}Matrix ans=A*exp(T,m);for(int i=1;i<=n;++i)printf("%lld ",ans.a[0][i]);printf("\n");}return 0;}
『 不可能 』只存在於蠢人的字典里
