题解：P12197 Hash Killer I

· · 题解

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

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