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); }