P12197 Hash Killer I 题解

很有意思的一道题，考虑只用 ab 来卡他。当 base 为偶数时，因为是自然溢出即模

2^{64}

，所以只要长度超过

64

就可以完美卡掉这个代码。当 base 为奇数时，考虑使用 Thue Morse 序列。这个序列的定义是，第一个字符为

0

然后不断复制自己然后按位取反加到最后面，比如说这样：

CPP

0
01
0110
01101001
0110100110010110

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

代码：

CPP

#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

项的方法。

P12197 Hash Killer I 题解

文章操作

相关推荐

评论

P12197 Hash Killer I 题解