题解：P12198 Hash Killer II

WorldMachine · 2025-04-16 16:24:41 · 题解

我赌他没卡我的单模哈希。

看起来有点难搞，但根据 Pollard-Rho 的结论，即生日悖论，期望随机 \mathcal O(\sqrt p) 个串就能有重复的哈希值，具体地说，是 \sqrt{\dfrac{\pi p}{2}}。那么随机输出就行了。

注意 l 不能开得太小了，不然总方案数到不了 \mathcal O(\sqrt p)。

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