問題概要
問題ページ
-
-
D - Bouquet
問題ページへ移動する
問題文
あかりさんは \(n\) 種類の花を \(1\) 本ずつ持っています。
あかりさんは、これらの花から \(1\) 本以上を選び、花束を作ろうとしています。
ただし、あかりさんは \(a\) と \(b\) の \(2\) つの数を苦手としていて、いずれかと一致するような本数の花からなる花束は作ることができません。
あかりさんが作ることのできる花束は何種類あるでしょうか。
\((10^9 + 7)\) で割った余りを求めてください。
ここで \(2\) つの花束は、一方では使われているが、
もう一方では使われていない種類の花があるとき、別の種類の花束であるとみなします。
制約
- 入力は全て整数である。
- \(2 \leq n \leq 10^9\)
- \(1 \leq a < b \leq \textrm{min}(n, 2 \times 10^5)\)
問題の考察
ACコード
import sys
def alg_combination_mod(n, r, mod):
r = min(n - r, r)
if r == 0:
return 1
else:
denominator = 1
for i in range(n, n - r, -1):
denominator = (denominator * i) % mod
molecule = 1
for i in range(1, r + 1):
molecule = (molecule * i) % mod
return denominator * pow(molecule, mod - 2, mod) % mod
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n, a, b = list(map(int, input().rstrip('\n').split()))
all_cnt = pow(2, n, mod)
a_cnt = alg_combination_mod(n, a, mod)
b_cnt = alg_combination_mod(n, b, mod)
print((all_cnt - a_cnt - b_cnt - 1) % mod)
if __name__ == '__main__':
solve()