對于每一次的操作用矩陣表示，這里的矩陣a是（n+1，n+1），初始化為一個單位矩陣
‘g’ num 操作，表示使第num個數增加1，使矩陣a的第num行最后一個元素增加1，即a[num][last]+=1
‘e’ num 操作，表示使第num個數變為0，使矩陣a的第num行全部變為0
即for(i=1:i<=last;i++) a[num][i]=0;
‘s’ num1，num2操作，表示使第num1和num2元素交換位置，使矩陣a 的第num1和num2行互換就可以了for(i=1:i<=last;i++) swap(a[num1][i],a[num2][i]);
最后結果就是a[i][n+1]
 #include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define maxn 102
int m,n;
void mul(__int64 sor1[][maxn],__int64 sor2[][maxn],__int64 des[][maxn])
   {
 for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
  {
des[i][j]=0;
for(int k=0;k<=n;k++)
if(sor1[i][k] && sor2[k][j])
des[i][j]+=sor1[i][k]*sor2[k][j];
 }
 }
void copy(__int64 sor[][maxn],__int64 des[][maxn])
{
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
des[i][j]=sor[i][j];
}
void multiply(__int64 sor[][maxn],__int64 des[][maxn],int n)
{
if(n<=0)
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
des[i][j]=0;
des[i][i]=1;
}
}
else if(n==1)
copy(sor,des);
/**//*else if(n==2)
mul(sor,sor,des);*/
else
{
__int64 tmp[maxn][maxn];
multiply(sor,tmp,n/2);
mul(tmp,tmp,des);
if(n%2)
{
copy(des,tmp);
mul(tmp,sor,des);
}
}
}
void swap(__int64 & a1,__int64 & a2)
{
__int64 tmp;
tmp=a1; a1=a2; a2=tmp;
}
void print(__int64 a[][maxn])
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
printf("%d ",a[i][j]);
printf("\n");
}
}
int main()
{
char cmd;
int k;
__int64 mat[maxn][maxn],ans[maxn][maxn];
while(scanf("%d%d%d",&n,&m,&k)!=EOF,n||m||k)
{
memset(mat,0,sizeof(mat));
for(int i=0;i<=n;i++)
mat[i][i]=1;
while(k--)
{
getchar();
cmd=getchar();
if(cmd=='s')
{
int id1,id2;
scanf("%d%d",&id1,&id2);
id1--,id2--;
for(int i=0;i<=n;i++)
swap(mat[id1][i],mat[id2][i]);
}
else if(cmd=='g')
{
int id;
scanf("%d",&id);
id--;
mat[id][n]++;
}
else
{
int id;
scanf("%d",&id);
id--;
for(int i=0;i<=n;i++)
mat[id][i]=0;
}
}
//print(mat);
multiply(mat,ans,m);
printf("%I64d",ans[0][n]);
for(int i=1;i<n;i++)
printf(" %I64d",ans[i][n]);
printf("\n");
}
}
|