哈希碰撞
这里提供一个计算随机撒点碰撞概率的程序
#include<iostream>
#include<random>
#define int long long
#define ld long double
using namespace std;
// 就是下降幂除以普通幂
ld calc1(int n, int d) {
ld res = 1;
int j = 0;
for(int i = d - n + 1; i <= d; i++) {
res = res * i;
while(j < n && res >= 1) { res /= d; ++j; }
}
while(j < n) { res /= d; ++j; }
return res;
}
// example
// 在值域 1e18 内撒 1e6 个点
int n = 1e6;
int d = 1e18;
signed main() {
// cin >> n >> d;
// 不碰撞的概率
cout << calc1(n, d) << endl;
return 0;
}