自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 23:13:38，当前版本为作者最后更新于2025-04-16 15:56:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我赌他没卡我的自然溢出。

对于 $b$ 为偶数的情况，只要串够长 $b^n$ 就变成 $0$ 了。

对于奇数的情况，Thue Morse 序列可以让它爆炸。

对于二进制串 $s$，定义 $\bar s$ 为按位翻转后的串。令 $0$ 阶 Thue Morse 序列 $t_0=\texttt{0}$，$t_n=t_{n-1}+\overline{t_{n-1}}$，有 $\text{hash}(t_n)=b^{2^{n-1}}\text{hash}(t_{n-1})+\text{hash}(\overline{t_{n-1}})$，$\text{hash}(\overline{t_n})=b^{2^{n-1}}\text{hash}(\overline{t_{n-1}})+\text{hash}(t_{n-1})$，记 $h_n=\text{hash}(t_n)-\text{hash}(\overline{t_n})$，有 $h_n=(b^{2^{n-1}}-1)h_{n-1}$。

由于 $b^{2^{n-1}}-1=(b-1)(b^{2^{n-2}}+1)(b^{2^{n-3}}+1)\dots(b+1)$，而 $b$ 是奇数，那么每一项都是偶数，故 $2^n|b^{2^{n-1}}-1$，那么 $2^{\frac{n(n+1)}{2}}|f_n$，对于 $n\ge11$，$\dfrac{n(n+1)}{2}>64$，自然溢出就爆炸了。

那么输出长度为 $2^{11}$ 的 Thue Morse 序列即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n = 1 << 11, l = n >> 1;
	printf("%d %d\n", n, l);
	for (int i = 0; i < n; i++) putchar('a' + (__builtin_popcount(i) & 1));
}