7K12 blog

猫でも分かるアルゴリズム解説

ABC 156 D - Bouquet

f:id:tkr987:20200709032620p:plain

https://atcoder.jp/contests/abc156/submissions/10570710

  •  \sum \ _nC_r = 2^n r=0を含むので注意

f:id:tkr987:20200709035247p:plain

文章を数式にすると _nC_1+_nC_2+ ... + _nC_n - _nC_a - _nC_bとなる。なんとなく前半が式変形できそうという気持ちになる。調べてみると二項係数の和は 2^nに等しいという情報が得られる。

https://mathtrain.jp/nikoubekijo

ただし、nが 10^9もあるので工夫せず累乗の計算をすると間に合わない。累乗の高速化として繰り返し二乗法というテクニックがあり、 O(\log n)で答えが求まる。

https://math.nakaken88.com/textbook/cp-binary-exponentiation-and-recursive-function/

組み合わせの計算はnが 10^9もあるのでメモ化を使った高速化を適用できないが、素直に - _nC_a - _nC_bを計算しても最大で O(2 \times 10^5)で計算出来るため問題ない。

したがって、 2^n - _nC_a - _nC_b - 1が答えになる(花0本=1通りの組み合わせを除外するのを忘れずに)

計算量は O(min(n, 2 \times 10^5))