题解：P12198 Hash Killer II

Merlin_Meow · 2025-04-16 22:09:37 · 题解

Analysis

单模哈希实际上是非常好卡的。

由生日悖论可知，对于一个模数为 p 的哈希，取 \sqrt{p} 次就大概率会发生哈希冲突。于是我们只需要胡乱输出随机字符就可以卡掉它。\sqrt{10^9+7}\approx 31629.78，为了保险我们直接取 10^5 次即可稳定通过。

Code

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    mt19937 RAND(time(0));
    int n = 100'000, l = 100;
    cout << n << " " << l << endl;
    for (int i = 1; i <= n; i++)
        cout << char(RAND() % 26 + 'a');
    cout << endl;
    return 0;
}