题解：P12198 Hash Killer II

Analysis

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

由生日悖论可知，对于一个模数为

p

的哈希，取

\sqrt{p}

次就大概率会发生哈希冲突。于是我们只需要胡乱输出随机字符就可以卡掉它。

\sqrt{10^9+7}\approx 31629.78

，为了保险我们直接取

10^5

次即可稳定通过。

Code

CPP

#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;
}

题解：P12198 Hash Killer II

文章操作

Analysis

Code

相关推荐

评论

题解：P12198 Hash Killer II