Bouquet [AtCoder Beginner Contest 156 D]

https://atcoder.jp/contests/abc156/tasks/abc156_d

前提知識

• mod素数上での計算（割り算）
• 繰り返し二乗法による累乗計算

解説

https://atcoder.jp/contests/abc156/submissions/10299907

本数制限がない場合を考えよう。
すると、N種類の花を使って作れる花束の数は2^N-1となる。
ある花をとるとらないの2通りがN個あるので、2^N通りであるが、1本は選ぶ必要があるので、
全部とらないとしている1通りを引いている。
答えはこれから、a本選んだときとb本選んだときを引いたものになる。

自分の実装ではmod10⁹+7を扱うためにmintを使用している。
競プロ界隈はmodを扱うための自作クラスをよく使う人がいて、自分もその一人。

2^Nの計算方法は、繰り返し二乗法を用いる。
やりかたはググってほしい。
ここを参考にしてもいい。
そのサイトでの知識は競プロでは必要になる。

count関数を作って、実装を考えよう。
count(x) := x本作る時の組み合わせ
これは二項係数のC(N,x)が答えになるが、この問題ではNがとても大きくて困る。
しかし、よく見るとxは10⁵くらいである。
よって、高校で習うような公式を使って計算することができる。

int N, A, B;
//---------------------------------------------------------------------------------------------------
mint count(int x) {
    // nCx
    mint res = 1;
    rep(i, 0, x) res *= N - i;
    rep(i, 1, x + 1) res /= i;
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B;

    mint ans = (mint(2) ^ N) - 1;
    ans -= count(A);
    ans -= count(B);
    cout << ans << endl;
}