P12197 Hash Killer I 题解

sunqihuan · 2025-10-29 23:08:47 · 题解

很有意思的一道题，考虑只用 ab 来卡他。当 base 为偶数时，因为是自然溢出即模 2^{64}，所以只要长度超过 64 就可以完美卡掉这个代码。当 base 为奇数时，考虑使用 Thue Morse 序列。这个序列的定义是，第一个字符为 0 然后不断复制自己然后按位取反加到最后面，比如说这样：

0
01
0110
01101001
0110100110010110

当这样重复到一定次数，自然溢出就被卡掉了！

代码：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    cout << (1 << 12) << " " << (1 << 11) << endl;
    for (int i = 1; i <= (1 << 12); i ++ ) putchar('a' + (__builtin_popcount(i) & 1));
    return 0;
}

其中 __builtin_popcount(i) & 1 便是一种生成这个序列第 i 项的方法。