矩阵快速幂，这里的模版就是计算A^n的，A为矩阵。
之前的矩阵快速幂貌似还是个更通用一些。
下面的题目解释来自 我只想做一个努力的人
@@@请注意 ，单位矩阵最初构造 行和列都要是（猫咪数+1）！！！然后按照分析的来，分析中矩阵的下标都是从0开始的。
无法理解的可自行构造案例的矩阵进行验证。
注意一些细节，有些数据要用64位，不然会wa。
//可能是因为原本的模版不适用 #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; int num;
struct matrix
{
long long a[][];
}origin,answ; matrix multiply(matrix x,matrix y)//矩阵乘法
{
matrix temp;
memset(temp.a,,sizeof(temp.a));//因为后面的代码变了，所以这里也要初始化了
for(int i=;i<=num;i++)
{
for(int k=;k<=num;k++)
{
if(x.a[i][k])//据说多加这么一句筛选一下就不超时了？
{
for(int j=;j<=num;j++)
{
temp.a[i][j]+=((x.a[i][k]*y.a[k][j]));
}
}
}
}
return temp;
} matrix calc(matrix a,int n)//矩阵快速幂——a^n
{
if(n==)return a;
matrix e;
for(int i=;i<=num;i++)
for(int j=;j<=num;j++)
e.a[i][j]=(i==j); while(n)
{
if(n&)
e=multiply(e,a);
n>>=;
a=multiply(a,a);
}
return e;
} int main()
{ // freopen("in.txt", "r+", stdin);
// freopen("out.txt", "w+", stdout);
int n,k,m;
char s[];
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
if(n==&&m==&&k==)break;
num=n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
origin.a[i][j]=(i==j); while(k--)
{
long long ii,jj;//这种数据也要64位
scanf("%s",s);
if(s[]=='g')
{
scanf("%lld",&ii);
origin.a[][ii]++;
}
else if(s[]=='s')
{
scanf("%lld%lld",&ii,&jj);
long long kk;
for(int iii=;iii<=n;iii++)
{
kk=origin.a[iii][ii];
origin.a[iii][ii]=origin.a[iii][jj];
origin.a[iii][jj]=kk;
}
}
else
{
scanf("%lld",&ii);
for(int iii=;iii<=n;iii++)
{
origin.a[iii][ii]=;
}
}
}
if(m==)//之前没考虑到这个？
memset(answ.a,,sizeof(answ.a));
else
answ=calc(origin,m);
int yi=;
for(int i=;i<=n;i++)
{
if(yi)
printf(" ");
printf("%lld",answ.a[][i]);
yi=;
}
puts("");
}
return ;
}