E

一年有$2^n$天
随机选择k个人
问所选的人中至少有两人生日相同的概率

数论

问题的答案为$1 - \frac{A_{2^n}^k}{2^{nk}}$

只需要约去分子分母中的2即可

分子形式为$2^n(2^n-1)…(2^n - k + 1)$,可以将$2^n$约去

分子中2的幂次可以在$O(logn)$内求出
即$f[2^n-1] - f[2^n - k + 1]$,
求(k-1)!的幂次即可