#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m, k;
long long init[102];
long long all[102][102];
long long tmp[102][102];
char ch[3];
long long na[102][102], nb[102][102], nc[102][102];

void binary(int k) {
	if(k == 1) {
		for(int i = 0; i <= n; ++i)
			for(int j = 0; j <= n; ++j)
				nc[i][j] = all[i][j];
	} else {
		binary(k / 2);
		for(int i = 0; i <= n; ++i) {
			for(int k = 0; k <= n; ++k) {
				nb[i][k] = 0;
				for(int j = 0; j <= n; ++j) {
					if(nc[i][j] && nc[j][k])
						nb[i][k] += nc[i][j] * nc[j][k];
				}
			}
		}
		if(k % 2) {
			for(int i = 0; i <= n; ++i) {
				for(int k = 0; k <= n; ++k) {
					nc[i][k] = 0;
					for(int j = 0; j <= n; ++j) {
						if(nb[i][j] && all[j][k])
							nc[i][k] += nb[i][j] * all[j][k];
					}
				}
			}
		} else {
			for(int i = 0; i <= n; ++i)
				for(int j = 0; j <= n; ++j)
					nc[i][j] = nb[i][j];
		}
	}
}

int main() {
	while(scanf("%d%d%d", &n ,&m, &k) && (n+m+k)!=0 ) {
		memset(init, 0, sizeof(init));
		memset(all, 0, sizeof(all));
		init[n] = 1;
		for(int i = 0; i <= n; ++i)
			all[i][i] = 1;
		
		for(int i = 0; i < k; ++i) {
			int nt = 0;
			scanf("%s", ch);
			if(strcmp(ch, "g") == 0)
				nt = 1;
			else if(strcmp(ch, "s") == 0)
				nt = 2;
			else
				nt = 3;
			int s1, s2;
			switch(nt) {
				case 1:
					scanf("%d", &s1);
					--s1;
					for(int i = 0; i <= n; ++i)
						all[i][s1] += all[i][n];
					break;
				case 2:
					scanf("%d%d", &s1, &s2);
					--s1, --s2;
					for(int i = 0; i <= n; ++i) {
						int t = all[i][s1];
						all[i][s1] = all[i][s2];
						all[i][s2] = t;
					}

					break;
				case 3:
					scanf("%d", &s1);
					--s1;
					for(int i = 0; i <= n; ++i)
						all[i][s1] = 0;
					break;
			}
		}
		binary(m);

		for(int i = 0; i < 1; ++i) {
			for(int k = 0; k <= n; ++k) {
				long long sum = 0;
				for(int j = 0; j <= n; ++j) {
					sum += init[j] * nc[j][k];
				}
				if(k < n)
					printf("%lld ", sum);
			}
			
		}
		putchar('\n');
	}
	return 0;
}

• Re:我晕，竟然有m = 0的数据，一直RE，原来是因为这个。 (0) MasterLuo 2009-05-20 18:40:10