ABC156 D Bouquet
答えをそのまま求めても$ O(N)となり間に合わない. そこで余事象を考えると, 問題の答えは$ \sum_{i=1}^n {}_n C _i - {}_n C _a - {}_n C _bとなる事がわかる. ここで$ \sum_{i=0}^n {}_n C _i = 2^nより, $ \sum_{i=1}^n {}_n C _i = 2^n - {}_n C _0 = 2^n - 1と変形できることがわかる. $ 2^nについては繰り返し二乗法を用いることで高速に計算できる. また, $ {}_n C _a, {}_n C _bについては数学で計算するように$ \frac{n(n-1)(n-2)...(n-i)(n-i+1)}{i(i-1)(i-2)...3 \cdot 2 \cdot 1}の$ iに$ a, bを代入して計算していけばよい. これは$ O(max(a, b))で計算することができる.
以上より, $ O(log N + max(a, b))でこの問題を解くことができた.