POJ-3735 : Training little cats

問題概要

N(<100)個の変数がある。x[i]を1増やす、x[i]を0にする、x[i]とx[j]を交換する、という長さK(<100)の操作列を1セットとする。操作列をM(<10^9)回繰り替えした後変数がどうなっているか求める問題。

解法

1回の反復で係数行列がどう変化分かるので後は行列累乗するだけでよい…のだけどこれだとO(log M * N^3)でTLEする。この係数行列はかなり疎で、定数項以外の係数は1か0しか出てこないので置換で表すことにする。つまり、1回の操作でa[i]はa[perm[i]] + cnst[i]となるようにperm, cnstを定める。ただしa[perm[i]]の部分は0にもなりうる。こうすると後はバイナリ法でO((log M + K)* N)となり間に合う。

acceptされたコード

#include <cstdio>
#include <vector>
using namespace std;

typedef long long int64;
const int MAX_N = 100;

int N, M, K;
vector<int> perm;
vector<int64> cnst;

bool init() {
	scanf("%d%d%d ", &N, &M, &K);
	if (N == 0) {
		return false;
	}

	perm.resize(N);
	for (int i = 0; i < N; ++i) {
		perm[i] = i;
	}
	cnst.assign(N, 0);

	for (int _ = 0; _ < K; ++_) {
		char op;
		scanf(" %c ", &op);
		if (op == 'g') {
			int idx;
			scanf("%d", &idx);
			--idx;
			++cnst[idx];
		}
		else if (op == 's') {
			int idx1, idx2;
			scanf("%d%d", &idx1, &idx2);
			--idx1; --idx2;
			swap(perm[idx1], perm[idx2]);
			swap(cnst[idx1], cnst[idx2]);
		}
		else {
			int idx;
			scanf("%d", &idx);
			--idx;
			cnst[idx] = 0;
			perm[idx] = -1;
		}
	}

	return true;
}

void composition() {
	vector<int> tmpPerm(N);
	vector<int64> tmpCnst(N);

	for (int i = 0; i < N; ++i) {
		tmpPerm[i] = perm[i] == -1 ? -1 : perm[perm[i]];
		tmpCnst[i] = (perm[i] == -1 ? 0 : cnst[perm[i]]) + cnst[i];
	}

	perm.swap(tmpPerm);
	cnst.swap(tmpCnst);
}

vector<int64> apply(const vector<int64>& xs) {
	vector<int64> ret(N);
	for (int i = 0; i < N; ++i) {
		ret[i] = (perm[i] == -1 ? 0 : xs[perm[i]]) + cnst[i];
	}
	return ret;
}

void solve() {

	vector<int64> start(N, 0);
	for (; M; M >>= 1) {
		if (M & 1) {
			start = apply(start);
		}
		composition();
	}
	for (int i = 0; i < N; ++i) {
		printf("%lld%c", start[i], i == N - 1 ? '\n': ' ');
	}
}

int main() {
	for (;init();) {
		solve();
	}
	return 0;
}