哈希碰撞

这里提供一个计算随机撒点碰撞概率的程序

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