Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

PKU 3735 : Trailing little cats

問題文 : Trailing little cats

解法 :
a_{ij} = i回目のセットでj番目のネコが持っているピーナッツの数, とすると, a_{ij}は以下の2つのいずれかとなる :

・a_{i-1σ(j)} + a_{i-1j}
・a_{i-1j}

ここで, f(i)を ベクトルa_{i-1}からベクトルa_iを作る操作とすると,
f(i + j) = f(i) + f(j), f(ki) = kf(i)が成立するので, この操作fは線形写像である.

ゆえに, 1個先の操作, 2個先の操作, ..., 2^k個先の操作を計算し, ダブリングっぽく操作を施すと O(k + nlogm)でこの問題を解くことが出来る.

コード :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long lint;
typedef vector<pair<int, lint> > P;

int n;

int in(void)
{
	int a;
	scanf("%d", &a);
	return (a);
}

P trans(P a, P b)
{
	P ret(n);
	
	for (int i = 0; i < n; i++) ret[i].first = -1;
	
	for (int i = 0; i < n; i++){
		if (~b[i].first){
			ret[i].first = a[b[i].first].first;
			ret[i].second = a[b[i].first].second + b[i].second;
		}
	}
	for (int i = 0; i < n; i++){
		if (ret[i].first == -1){
			ret[i].first = -1;
			if (!ret[i].second) ret[i].second = b[i].second;
		}
	}
	return (ret);
}

P succ(P cat, int k)
{
	P norm(cat.size());
	
	for (int i = 0; i < n; i++) norm[i].first = i;
	
	while (k){
		if (k & 1){
			norm = trans(norm, cat);
		}
		cat = trans(cat, cat);
		k >>= 1;
	}
	
	return (norm);
}

int main()
{
	int m, k;
	
	while (scanf("%d %d %d", &n, &m, &k), n){
		P cat(n);
		
		for (int i = 0; i < n; i++) cat[i].first = i;
		
		for (int i = 0; i < k; i++){
			char q[32];
			scanf("%s", q);
			
			if (q[0] == 'g'){
				cat[in() - 1].second++;
			}
			else if (q[0] == 'e'){
				int var = in() - 1;
				cat[var].first = -1;
				cat[var].second = 0;
			}
			else {
				swap(cat[in() - 1], cat[in() - 1]);
			}
		}
		cat = succ(cat, m);
		
		for (int i = 0; i < n; i++){
			printf("%lld%c", cat[i].second, i == n - 1 ? '\n' : ' ');
		}
	}
	
	return (0);
}