AGC006C: Rabbit Exercise

https://beta.atcoder.jp/contests/agc006/tasks/agc006_c

おもしろかったので別に記事書きました。

まず簡単な計算をすると、ai,ai+1,ai+2と場所の期待値が求まっており、ai+1が行動するとき、ai+1の期待値はai+1→ai+ai+2-ai+1となることがわかります。
次の場所の期待値は前の場所の線型結合の和で表せるので行列累乗すればO(N^3logK)で求められます。
しかしN=10^5なので到底間に合いません。
ここでai+1-aiとai+2-ai+1に注目すると、ai+1-ai→ai+2-ai+1,ai+2-ai+1→ai+1-aiになっていることがわかります。つまりswapされたことになっています。なのでM回swapされた後の位置は置換行列で求められ、置換行列同士の掛け算は一回あたりO(N)で済むのでO(NlogK)でK回おこなかった後の場所もわかります。あとは累積和するだけです。

4項の関係を差のswapに言い換えるのは難しいですね…。
こんなの計算できるのはシンプルに驚きでした。

int N, M; ll K;
ll A[MAX_N];
 
vi ordfun(const vi& vec1, const vi& vec2) {
	vi res(N - 1);
	rep(i, 0, N - 1) {
		res[i] = vec2[vec1[i]];
	}
	return res;
}
 
vi ordpow(vi vec, ll K) {
	if(K == 1) return vec;
	else {
		vi tmp = ordpow(vec, K / 2);
		tmp = ordfun(tmp, tmp);
		if(K % 2 == 0) return tmp;
		else return ordfun(tmp, vec);
	}
}
 
void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	cin >> M >> K;
	vector<int> vec(N - 1);
	rep(i, 0, N - 1) vec[i] = i;
	rep(i, 0, M) {
		int a;
		cin >> a; a--;
		swap(vec[a], vec[a - 1]);
	}
	vec = ordpow(vec, K);
	ll cur = A[0];
	rep(i, 0, N) {
		cout << cur << "\n";
		if(i != N - 1) {
			cur += A[vec[i] + 1] - A[vec[i]];
		}
	}
}