Edit

【pythonでABC156を解説】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()

プログラミング

-Edit