/* * POJ_3735.cpp * * Created on: 2013年11月19日 * Author: Administrator */ #include#include #include #include #include using namespace std; #define maxn 105 long long n, k, m;//A是n*n阶的矩阵,k是要求的sum = A^1 + A^2 +.....A^k; m 是被模的元素 struct Mat { long long val[maxn][maxn]; void unit() { //单位矩阵 zero();//这一个千万别漏了,否则会TLE for (int i = 0; i < maxn; i++) val[i][i] = 1; } void zero() { //零矩阵 memset(val, 0, sizeof(val)); } } A,T;//A: 初始矩阵,T: 转置矩阵 Mat operator *(const Mat &a, const Mat &b) { //矩阵乘法 Mat tmp; tmp.zero(); for (int k = 0; k <= n; k++) {//***要注意矩阵的起始编号,这里是从0开始的,也有从1开始的 for (int i = 0; i <= n; i++) if (a.val[i][k]) for (int j = 0; j <= n; j++) { tmp.val[i][j] += a.val[i][k] * b.val[k][j]; } } return tmp; } Mat operator ^(Mat x, int n) { //矩阵快速幂 Mat tmp; tmp.zero(); tmp.unit(); while (n) { if (n & 1) tmp = tmp * x; x = x * x; n > >= 1; } return tmp; } void init(){ A.zero(); A.val[0][0] = 1; T.unit(); } int main(){ char s[5]; while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF,n||m||k){ init(); while(k--){ scanf("%s",s); int a,b; if(s[0] == 'g'){ scanf("%d",&a); T.val[0][a]++; }else if(s[0] == 'e'){ int i; scanf("%d",&a); for(i = 0 ; i <= n ; ++i){ T.val[i][a] = 0; } }else{ int i; scanf("%d%d",&a,&b); for(i = 0 ; i <= n ; ++i){ swap(T.val[i][a],T.val[i][b]); } } } Mat ans = A*(T^m); int i; for(i = 1 ; i <= n ; ++i){ printf("%lld ",ans.val[0][i]); } printf("\n"); } return 0; }