No.017 D

残りサプリメントが $n$ 個のときの組み合わせの数を $C(n)$ とすると,

$$C(n) = C(n-1) + C(n-2) + \cdots + C(n-k)$$

となる. ただし, $k$ は同じ味のサプリメントが現れない最大の数である. この数はしゃくとり法で計算する.

これを愚直に計算すると $O(N^2)$ の計算量になるので, Binary Indexed Tree を使って区間の足し算を高速化する.