けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 156 D - Bouquet (緑色, 400 点)

二項係数を使いこなすっ!!!

問題へのリンク

問題概要

 N 種類の花束から何個か選ぶ方法のうち、それが  A 個でも  B 個でもないようなものが何通りあるかを 1000000007 で割ったあまりを求めよ。

制約

  •  2 \le N \le 10^{9}
  •  1 \le a \lt b \le \min(N, 2 \times 10^{5})

考えたこと

結局、 N 個のものからいくつか選ぶ方法 ( 2^{N} 通りある) のうち、以下の場合を除けば OK。

  • 何も選ばない場合:  1 通り
  •  A 個選ぶ場合: {}_{N}{\rm C}_{A} 通り
  •  B 個選ぶ場合: {}_{N}{\rm C}_{B} 通り

よって求める答えは

  •  2^{N} - {}_{N}{\rm C}_{A} - {}_{N}{\rm C}_{B} - 1 通り

となる。。。

これで一瞬、「なんだ簡単やん」となると詰まってしまう。下記事で最初に描いたような方法で解ける気がしてしまう。

drken1215.hatenablog.com

ただし、これができるのは、  {}_{N}{\rm C}_{K} を求めるのに、

  •  N \le 10^{5} くらい
  •  K \le 10^{5} くらい

という場合に限るのだ。今回は  N \le 10^{9} なのでもう少し工夫する必要がある。

NCK の K が小さいとき

しかしながら、 N が大きくても  K が小さければ求めることができる。具体的には、

 {}_{N}{\rm C}_{K} = \frac{N(N-1)\dots(N-K+1)}{K!}

であることを利用すれば、 O(K) 回の演算で計算することができるのだ。

#include <bits/stdc++.h>
using namespace std;

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;

mint calc(long long N, long long K) {
    mint res = 1;
    for (long long n = 0; n < K; ++n) {
        res *= (N - n);
        res /= (n + 1);
    }
    return res;
}

int main() {
    long long N, A, B;
    cin >> N >> A >> B;
    mint res = modpow(mint(2), N) - 1;
    res -= calc(N, A) + calc(N, B);
    cout << res << endl;
}