https://atcoder.jp/contests/abc156/tasks/abc156_d
前提知識
解説
https://atcoder.jp/contests/abc156/submissions/10299907
本数制限がない場合を考えよう。
すると、N種類の花を使って作れる花束の数は2N-1となる。
ある花をとるとらないの2通りがN個あるので、2N通りであるが、1本は選ぶ必要があるので、
全部とらないとしている1通りを引いている。
答えはこれから、a本選んだときとb本選んだときを引いたものになる。
自分の実装ではmod109+7を扱うためにmintを使用している。
競プロ界隈はmodを扱うための自作クラスをよく使う人がいて、自分もその一人。
2Nの計算方法は、繰り返し二乗法を用いる。
やりかたはググってほしい。
ここを参考にしてもいい。
そのサイトでの知識は競プロでは必要になる。
count関数を作って、実装を考えよう。
count(x) := x本作る時の組み合わせ
これは二項係数のC(N,x)が答えになるが、この問題ではNがとても大きくて困る。
しかし、よく見るとxは105くらいである。
よって、高校で習うような公式を使って計算することができる。
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; }