ABC156_D – Bouquet

問題

D - Bouquet

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

提出

Submission #44836898 - AtCoder Beginner Contest 156

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

解けた

以下、解法を書く。
それぞれの花において選ぶ/選ばないの2つがあり得るので、花束の種類としては$2^N-1$になる(全て選ばないの選択は除くため1少なくなる)。
これから、$_NC_a$と$_NC_b$を引くと答えになる。

難しいところは$_NC_x$をどうやって求めるかという点。
$N$が大きいので$1…N$までの階乗を求める方法は使えない。
$_NC_x$を以下のようにみると、x回で求まる。
$$ \frac{N*(N-1)…(N-(x-1))}{x*(x-1)*…*1}$$