链接
传送门
题意
一年有\(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;
}
|