Codeforces 711E ZS and the Birthday Paradox

链接

传送门

题意

一年有$2^n(1 \leq n \leq 10^{18})$天,有$k(2 \leq k \leq 10^{18})$个人,求至少两人生日相同的概率。

思路

当$k > 2^n$时,$p=1$。

当$k \leq 2^n$时,有$$p=1-\frac{(2^n - 1)(2^n - 2) \cdots (2^ n - k + 1)}{2^{(k - 1)n}}=\frac{b-a}{b}$$

可以在$O(\log k)$的时间内求出$\gcd(a,b)$。

对于$a$,若$k-1 > mod$,则$a=0$。否则可以枚举求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
using namespace std;
typedef long long LL;
const LL mod = 1000003;
LL pow_mod(LL x, LL k) {
LL res = 1, cur = x;
while (k) {
if (k & 1) {
res = res * cur % mod;
}
cur = cur * cur % mod;
k >>= 1;
}
return res;
}
int main() {
LL n, k;
scanf("%lld%lld", &n, &k);
if (n < 63 && (1LL << n) < k) {
puts("1 1");
return 0;
}
LL tmp = 0, pow2_n = pow_mod(2, n);
for (LL i = 2; i < k; i <<= 1) {
tmp += (k - 1) / i;
}
LL gcd_inv = pow_mod(pow_mod(2, mod - 2), tmp);
LL a = 1, b = pow_mod(pow2_n, k - 1) * gcd_inv % mod;
if (k > mod) {
a = b;
} else {
for (int i = 1; i < k; ++i) {
a = a * (pow2_n - i + mod) % mod;
}
a *= gcd_inv;
a = ((b - a) % mod + mod) % mod;
}
printf("%lld %lld\n", a, b);
return 0;
}

支付宝扫码领红包