题意：有n个猫，开始的时候每个猫都没有坚果，进行k次操作，g x表示给第x个猫一个坚果，e x表示第x个猫吃掉所有坚果，s x y表示第x个猫和第y个猫交换所有坚果，将k次操作重复进行m轮，问最后这n个猫各自有多少坚果。
题解：构造(n+1)*(n+1)的单位矩阵，data[i][j]表示第i个猫与第j个猫进行交换，最后一列的前n项就是每个猫的坚果数目，s操作就交换对应行，矩阵快速幂时间复杂度O(n^3*log2(m))会超时，我们注意到在n*n的范围内每一行只有一个1，利用稀疏矩阵的乘法优化可以优化时间复杂度至O(n^2*log2(m))。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
struct matrix
{
ll data[][];
};
matrix ma;
ll n,m,k,x,y;
matrix multi(matrix a,matrix b)
{
matrix c;
memset(c.data,,sizeof(c.data));
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
{
//稀疏矩阵的乘法优化
if(a.data[i][j]) //一个数一个数加进去
for(int k=; k<=n; k++)
//注意这里的ijk已经改变位置
c.data[i][k]+=a.data[i][j]*b.data[j][k];
}
return c;
}
matrix init(matrix *a)
{
memset((*a).data,,sizeof((*a).data));
for(int i=;i<=n;i++)
(*a).data[i][i]=;
//矩阵乘法的意义：
//注意这里(*a).data[n][n]=1; 他的意义是继承上次操作的值
//(*a).data[i][j]=1;继承的是交换的值 两个值加起来就是新的值
return *a;
}
matrix pow1(matrix a,ll b)
{
matrix ans;
init(&ans);
while(b)
{
if(b&)
{
ans=multi(ans,a);
b--;
}
b>>=;
a=multi(a,a);
}
return ans;
}
void debug(matrix ans)
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
printf("%lld%c",ans.data[i][j],j==n?'\n':' ');
}
int main()
{
while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF)
{
if(n==&&m==&&k==) break;
char op[];
init(&ma);
while(k--)
{
scanf("%s%lld",op,&x);
x--;
if(op[]=='g')
{
ma.data[x][n]++;
}
else if(op[]=='s')
{
scanf("%lld",&y);
y--;
for(int i=;i<=n;i++)
swap(ma.data[x][i],ma.data[y][i]);
}
else if(op[]=='e')
{
for(int i=;i<=n;i++)
ma.data[x][i]=;
}
}
matrix ans=pow1(ma,m);
//debug(ans);
for(int i=;i<n;i++)
printf("%lld%c",ans.data[i][n],i==n-?'\n':' ');
}
return ;
}