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