CWOI S C0216 C 進化

題面使用 openssl enc -aes256 -base64 加密。

U2FsdGVkX1/8kkB98g1dG8Xj90RjkCx5lV3FFbUW4At6UhbCwragHBKknZmcd5R2
BsslkKPSQgKrZquzm5UNOENBOSIiXrCvZJ6UhhpQ02NsLO7W4nN+n78dURC7Njtz
hgTJoyRIHlxWB8EF+TozeifCU82nUbE+wyFDUCeJkDLeM3uE4Cvj51TAxILJN4gk
YJKvkAkVAUliBjjEuMZr3yM2SAGZoeasaLNLo2UGvUC8BLyB78KfnF2QyjHFVncg

這道題實際上是 D 題

首先，注意到每一位對於答案的貢獻是獨立的，如 01100 進化 $T$ 次後結果和 01000 進化 $T$ 次異或上 00100 進化 $T$ 次相同。所以可以單獨考慮每一位對於答案的貢獻，當然，如果某一位為 0 的話不對答案產生貢獻。故我們只考慮只有一個 1 的情況。

我們先假設這個串的長度是無限的，永遠不會達到邊界。列舉一個長度為 $T$ 的 +- 串，遇到 + 表示左移，遇到 - 表示右移，總共有 $2^T$ 種可能的貢獻。設有 $k$ 個 +， $T-k$ 個 -，則對 $2k - T$ 這個位置做貢獻。反過來，對於 $2k - T$ 這個位置做貢獻的就有 $\binom{T}{k}$ 個。當 $\binom{T}{k} \bmod 2 = 0$ 時做的貢獻互相抵消，不做貢獻。由盧卡斯定理，

$$\binom{T}{k}\bmod 2 = \binom{\left\lfloor\frac{T}{2}\right\rfloor}{\left\lfloor\frac{k}{2}\right\rfloor} \cdot \binom{T\bmod 2}{k\bmod 2}\bmod 2$$

當且僅當 $T \operatorname{or} k = T$，即 $k$ 是 $T$ 的子集時， $\binom{T}{k} \bmod 2 = 1$ 產生貢獻。我們可以把 $T$ 二進位制拆分，每次處理進化 $2^x$ 步的情況，這樣產生貢獻的 $k$ 只有 $k=0$ 和 $k=T$，總共進化 $\log T$ 次。

接下來我們考慮怎麼處理這個到達邊界的情況。我們構造一個環：

  a_0, a_1, a_2, a_3, ... a_n-1,
0,                              0,
  a_0, a_1, a_2, a_3, ... a_n-1,

考慮進化一次。對於所有的 $a_1$ 到 $a_{n-2}$，結果和對原串相同，對於 $a_0$ 和 $a_{n-1}$，由於旁邊是 $0$，結果也和原串相同。對於 $0$，由於左右兩邊相同，結果仍然為 $0$。故對於這樣的環，進化的結果和對原序列的結果相同。這樣就完美解決了到達邊界的問題。

程式碼：

int main()
{
	long long T;
	int N;
	scanf("%lld%d", &T, &N);
	std::vector<bool> a(N);
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%1d", &x);
		a[i] = x;
	}

	int n = N * 2 + 2;

	std::vector<bool> b;
	b.reserve(n);
	b.insert(b.end(), a.begin(), a.end());
	b.push_back(0);
	b.insert(b.end(), a.rbegin(), a.rend());
	b.push_back(0);

	while (T) {
		auto t = T & -T;
		T -= t;
		t %= n;

		std::vector<bool> c(n);

		for (int i = 0; i < n; i++) {
			if (!b[i]) continue;
			c[(i + t) % n] = !c[(i + t) % n];
			c[(i + n - t) % n] = !c[(i + n - t) % n];
		}

		b = c;
	}

	for (int i = 0; i < N; i++) {
		printf("%d", (int)b[i]);
	}
	printf("\n");
}