Codeforces Round #369 (Div. 2) E. ZS and The Birthday Paradox

問題

codeforces.com

整数 n, k が与えられる。

p = 2^n として, 1 - (p! / p^k * (p-k)!) の分母と分子を求めよ。ただし分母と分子は非常に大きな値になることがあるので, 10^6+3 で割ったあまりを求める。
(本当は p < k の場合は場合分けしないといけない)

解法

上では p! / p^k * (p-k)! と書きましたが, p*(p-1)*...*(p-k+1) / p^k と書く方が考えやすいです。

まず分母のほうから考えましょう。p^k を考えるだけなら簡単に出来ます。ただ, 分子で割られるので, そこがちょっと注意です。p が必ず偶数であることに注意すると, 2 で割られる回数は, p の分の n 回と, (p-1) * ... * (p-k+1) の分(これは k-1 にいくつの 2 の成分が含まれているかで求められる)です。

次に分子です。最終的に 10^6+3 で割ったあまりを求めるわけなので, k > 10^6+3 である場合は, 上記の掛け算の結果は 0 です。そうでない場合は, 直接計算すれば良いでしょう。2^m の成分がありますが上と同じように k-1 に含まれる 2 の成分の数分だけ割り算すれば良いです。

const int MOD = 1e6+3;

ll mod_pow(ll x, ll p, ll MOD) {
    ll a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    return mod_pow(a, m-2, m);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    if (n <= 61 && 1ll<<n < k) {
        cout << "1 1" << endl;
        return 0;
    }
    // 分母を求める
    ll mother = 1;
    // 減らされる分母の数
    ll cnt = n;
    {
        ll K = k-1;
        while (K) {
            cnt += K/2;
            K /= 2;
        }
        mother = mod_pow(2, n, MOD);
        mother = mod_pow(mother, k, MOD);
        mother *= mod_pow(mod_inverse(2, MOD), cnt, MOD);
        mother %= MOD;
    }
    // 分子を求める
    ll child = 1;
    {
        if (k >= MOD) child = 0;
        else {
            ll first = mod_pow(2, n, MOD);
            for (int i = 0; i < k; i++) {
                (child *= first-i) %= MOD;
            }
            if (child < MOD) child += MOD;
        }
        // 2 で割りまくる作業をする
        (child *= mod_pow(mod_inverse(2, MOD), cnt, MOD)) %= MOD;
    }
    child = (mother-child+MOD)%MOD;
    cout << child << " " << mother << endl;
    return 0;
}