ABC156 D - Bouquet - あっとのTECH LOG

問題原文

問題要旨

$N$ 本の区別可能な花から、１つ以上を選んで花束をつくる。ただし、 $A$ , あるいは $B$ と一致する本数を選ぶことはできない。作りうる花束の種類数を求めよ。ただしそのような物が無い場合には 0 とせよ。

$2 \leq N \leq 10^{9}$
$1 \leq A ＜ B \leq min(N, 10^{5})$

解法

逆元コンビネーションを用いて、 [tex: 2^{N} - {}NC_A - {}NC_B - 1] をすれば終わりに見える。。。
が、 $N$ が大きすぎていつも通りに ${}_nC_r = \frac{n!}{r!(n-r)!}$ とはできない。

ということで、 $A, B$ の制約が小さいことに注目し、 ${}_5C_3 = \frac{5・4・3}{3!}$ のように計算すればできる。
「最低１本は使わないといけない」ことと、「花束が作れないときは０とする」ことに気をつける。

実装

逆元部分は雑にやってもまぁ間に合う。

from math import factorial
N, A, B = map(int, input().split())
MOD = 10 ** 9 + 7

def calc(n):
    ret = 1
    for i in range(n):
        ret = ret * (N - i) % MOD
    return ret * pow(factorial(n), MOD - 2, MOD) % MOD

print(max(0, (pow(2, N, MOD) - ((calc(A) + calc(B)) % MOD) - 1) % MOD))

感想

ちょっとびっくりした。
特異な制約を見逃さない ようにする。