自动搬运

查看原文

来自洛谷，原作者为

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

搬运于2025-08-24 23:13:38，当前版本为作者最后更新于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);
}