我们看到这个题，很容易想到矩阵快速幂的做法。因为题目中两个条件实在太显眼：
- All the cats perform a sequence of these moves and must repeat it \(m\) times!
- \(m\leq 10^{10}\)
一个相同的操作，做 \(10^{10}\) 次，肯定是矩阵快速幂，问题就是我们如何把三个操作转化为 \((n+1)\times (n+1)\) 的矩阵 \(opt\)，\(opt\) 一开始是一个单位矩阵。
首先我们先确定一个 \(ans\) 矩阵，\(ans_{1,i}\) 表示第 \(i\) 只猫的花生数。联想到花生米@花少北。 那么一开始矩阵就是长这样：
\[\begin{bmatrix}0&\cdots&0\end{bmatrix}
\]
我们先来分析三个操作：
g x。给第 \(x\) 只猫加一颗花生，我们可以采用一个小技巧：扩充矩阵。我们先把 \(ans\) 矩阵变化一下，变成 \(n\) 个 \(0\)，\(1\) 个 \(1\)，如下：
\[\begin{bmatrix}0&\cdots&0\ 1\end{bmatrix}
\]
那么我们只需要给 \(opt_{n+1,x}\) 加上一个 \(1\)，就可以满足这个要求。因为在乘法是会有 \(ans_{i,x}+=ans_{1,n+1}\times opt_{n+1,x}\)。
-
e x。这个操作最简单。我们直接清空 \(opt\) 中第 \(x\) 列即可。 -
s x y。交换操作也很简单，也就是把 \(opt\) 中 \(x,y\) 两列交换一下即可。
最后快速幂计算即可。
注意一下本题中这是一个稀疏矩阵，我们可以用一个小优化来通过老爷机的评测。 详情见代码注释。
//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=110;
int n,m,k;
struct matrix {
long long data[MAXN][MAXN];
int col,row;
void clear() {
col=row=0;
for(int i=1;i<=n+1;i++) {
for(int j=1;j<=n+1;j++) {
data[i][j]=0;
}
}
}
void initialize() {
clear();
col=row=n+1;
for(int i=1;i<=n+1;i++) {
data[i][i]=1;
}
}
inline matrix operator *(matrix& b)const {
matrix ans;
ans.clear();
for(int i=1;i<=col;i++) {
for(int k=1;k<=row;k++) {
if(data[i][k]==0) continue;//这里有一个小优化~
for(int j=1;j<=b.row;j++) {
ans.data[i][j]+=data[i][k]*b.data[k][j];
}
}
}
ans.col=col;
ans.row=b.row;
return ans;
}
};
matrix ans;
matrix opt;
inline void qpow(int y) {
while(y) {
if(y&1) {
ans=ans*opt;
}
opt=opt*opt;
y>>=1;
}
}
signed main() {
while(1) {
scanf("%d%d%d",&n,&m,&k);
if(n==0&&m==0&&k==0) break;
ans.clear();
ans.col=1;
ans.row=n+1;
for(int i=1;i<=n;i++) {
ans.data[1][i]=0;
}
ans.data[1][n+1]=1;
opt.initialize();
for(int i=1;i<=k;i++) {
char ch[5];
int x,y;
scanf("%s",ch);
if(ch[0]=='s')
scanf("%d%d",&x,&y);
else
scanf("%d",&x);
if(ch[0]=='s') {
for (int j=1;j<=n+1;++j)
swap(opt.data[j][x],opt.data[j][y]);
}
if(ch[0]=='g') {
opt.data[n+1][x]++;
}
if(ch[0]=='e') {
for (int j=1; j<=n+1;++j)
opt.data[j][x]=0;
}
}
qpow(m);
for(int i=1;i<=n;i++) {
printf("%lld ",ans.data[1][i]);
}
printf("\n");
}
return 0;
}