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

問題概要

$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;
}