Sengxian's Blog

题目地址

描述

某个星球有一年 $2^n(1\le n\le {10}^{18})$ 天，现在抽取 $k(1\le k\le {10}^{18})$ 个人，问你至少有两个人生日为同一天的概率是多少？假设答案为 $\frac A B, A\perp B$，你需要输出的是 $\frac {A\bmod {10}^6 + 3} {B \bmod {10}^6 + 3}$。

分析

如果 $2^n<k$，根据鸽笼原理，必定存在两个人的生日处于同一天，直接输出 1 1。

下面假设 $2^n\ge k$。
直接算至少两个人生日相同的概率并不好算，我们算没有两个人生日相同的概率。首先固定第一个人的生日，则第二个人有 ${2^n - 1}$ 种选择，第三个人有 $2^n - 2$ 种选择，可得没有两个人生日相同的概率：

所以至少有两个人生日相同的概率为：

假设 $\bar P = \frac a b$，则 $P = \frac {b - a} b$，题目要求先化为最简形式（互质）再取模，根据 $\gcd(a, b) = \gcd(b - a, b)$，我们只需要求出 $\frac a b$ 的最简形式取模即可，这是因为：

由于 $\gcd(a, b) = \gcd(b - a, b)$，所以我们可以先算 $\frac a b$ 的最简形式取模，再用 1 来减，否则是不能够取模了之后再用 1 来减的。

我们现在求 $\bar P$，观察发现 $\gcd$ 一定是 $2$ 的幂，而且分母中的 $2$ 明显比分子中的 $2$ 要多，我们考虑求分子中有多少个 $2$，即能整除分子的最大的 $2^x$。我们的思路是求出分子分母的模，然后乘上 $\gcd$ 的逆元。

我们发现这样一个事实，如果有最大的 $m$ 使得 $2^m$ 能整除 $x\le 2^n$，那么它也是最大的 $m$ 使得 $2^m$ 能整除 $2^n - x$，反过来也成立。证明十分简单，对于 $x$ 来说，最大的 $2^m$ 就是 $\mathrm{lowbit}(x)$，而使用 $2^n > x$ 来减 $x$ 的话，必定有

现在我们就是要求 $(k - 1)!$ 中有多少个 $2$ 以得到 $\gcd$，根据 Legendre's formula，可以在 $O(\log k)$ 的时间内求出，而使用 __builtin_popcountll() 的话更是可以除一个很大的常数。

接下来我们要算分子，如果 $k - 1\ge \mathrm{modu}$，分子必然为 $0$，因为必然存在模的倍数。只剩下 $k - 1< \mathrm{modu}$ 的情况，这样分子就可以在至多 $O(\mathrm{modu})$ 的时间内算出。

接着算分母 $2^{(k - 1)n}$，发现 $(k - 1)n$ 会溢出，费马小定理来帮忙，只需要算 $(k - 1)n \bmod \mathrm{modu} - 1$ 的值就行了。

剩下的工作就是乘逆元，然后用 1 来减就行了。

P.S.：真是个数论综合知识运用的好题啊，我考试就是卡在转换到 $(k - 1)!$ 这一步了。

代码

//  Created by Sengxian on 08/30/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 711E 数论
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int modu = 1000003;
ll n, k;

inline ll mod_mul(ll a, ll b, int modu = ::modu) {
    ll res = 0;
    while (b) {
        if (b & 1) (res += a) %= modu;
        (a <<= 1) %= modu;
        b >>= 1;
    }
    return res;
}

inline ll mod_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) (res *= a) %= modu;
        (a *= a) %= modu;
        b >>= 1;
    }
    return res;
}

int main() {
    scanf("%lld%lld", &n, &k);
    if (n <= 62 && k > (1LL << n)) return puts("1 1\n"), 0;
    ll num = 1, deno = 0, pow = 0, inv;
    // cal gcd (2 ^ pow)
    pow = k - 1 - __builtin_popcountll(k - 1);
    // cal numerator
    if ((k - 1) < modu) {
        ll tmp = (mod_pow(2, n) + modu - 1) % modu;
        for (int i = 0; i < k - 1; ++i) {
            (num *= tmp) %= modu;
            (tmp += modu - 1) %= modu;
        }
    } else num = 0;
    // cal denominator 2 ^ n(k - 1)
    deno = mod_pow(2, mod_mul(n, k - 1, modu - 1));
    // cal inv of gcd
    inv = mod_pow(mod_pow(2, pow), modu - 2);

    (num *= inv) %= modu, (deno *= inv) %= modu;
    printf("%lld %lld\n", (deno - num + modu) % modu, deno);
    return 0;
}