解説放送ではライブラリを使って解いていたので自分用にまとめてみました

問題概要

$n$ 種類の花の中から $1$ 本以上を選ぶ場合の数を求める。
ただし、ちょうど $a , b$ 本になる場合は除く。
また、答えが非常に大きくなることがあるので $(10^{9}+7)$ で割った値を出力する。

考察

この問題、答えとなる数式自体は簡単で、 $2^{n}-1-nC _ {a}- nC _ {b}$ となり最終的にこれを求めることになります。

$2^{n}$ : すべての花の選び方
$1$ : $0$ 本選ぶの時の場合の数
$nC _ {a} , nC _ {b}$ : $n$ 本の花から $a , b$ 本選ぶ場合の数

ここで、 $2^{n}$ は、繰り返し2乗法を使えば高速に求められます。
しかし、問題なのは $nC _ {a} , nC _ {b}$ の方です。

組み合わせの公式を用いると

$\displaystyle{ nC _ {r} = \frac{n(n-1)(n-2)...(n-r+1)}{r!} }(mod10^{9}+7)$

となっていて、除算が含まれます。この場合普通に $mod$ をとることが出来ません。

除算で $mod$ をとる場合には逆元というものを用いることで求めることができます。

フェルマーの小定理より
$p$ を素数、 $a$ を $p$ の倍数でない任意の整数としたとき
$a^{p-1}\equiv1$ $(mod$ $p)$

これより
$a^{p-2}\equiv\frac{1}{a}$ $(mod$ $p)$

となるので、先ほどの組み合わせの公式 $\frac{1}{r!}$ $(mod10^{9}+7)$ が $r!^{10^{9}+7-2}$ $(mod10^{9}+7)$ と等価であるとみることが出来ます。

以上のことから求める式が以下のようになります

$\displaystyle{ nC_{r}=(n(n-1)(n-2)...(n-r+1))r!^{10^{9}+7-2} }(mod10^{9}+7)$

これで除算が消えたので $mod$ をとって計算することが出来ます。

実装

これまでのことを実装すると以下のようになります

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

const int mod = 1000000007;

//繰り返し2乗法
long long powmod(long long a, long long b){
    long long c = 1;
    while(b){
        if(b & 1) c = a * c % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return c;
}

//組み合わせを求める
long long nCr(long long n, long long r){
    long long x = 1, y = 1;
    //x : n*(n-1)*(n-2)*...*(n-r+1)
    //y : r!
    for(int i = 0; i < r; i++){
        x = x * (n - i) % mod;
        y = y * (i + 1) % mod;
    }
    //逆元をかけてmodをとる
    return x * powmod(y, mod - 2) % mod;
}

int main()
{
    long long n, a, b;
    cin >> n >> a >> b;
    long long ans = powmod(2, n) - 1 - nCr(n, a) - nCr(n, b);

    //引き算なのでmodの取り方に注意
    cout << (ans % mod + mod) % mod << endl;
    return 0;
}