CodeChef August Challenge 2020 - Subsequence Frequency Counting

• 問題
• AC

数列$(A_i)$が整数$x$を$c_x$個含むとする。また、整数$x$が代表になるような部分列でちょうど$k$個の$x$を含むものの総数を$f(x, k)$とする。$f(x, k)$を二項係数で表すと、以下のようになる:

$$f(x, k) := \biggl( \sum_{i=0}^{k-1} \binom{c_1}{i}...\sum_{i=0}^{k-1}\binom{c_{x-1}}{i} \biggr) \binom{c_x}{k} \biggl(\sum_{i=0}^{k}\binom{c_{x+1}}{i} ... \sum_{i=0}^{k}\binom{c_N}{i} \biggr)$$

$f(x, k)$を$N$通りの引数について足せばよいが、毎回すべての二項係数を掛け算していては間に合わない。そこで、$\operatorname{dp}[x] := \sum_i \binom{c_x}{i}$という形の列をセグメント木で持っておくことを考える。$\operatorname{dp}$のそれぞれの値が適切な$k$に対応していれば、$f(x, k)$は$\operatorname{dp}[1...x-1]$の積と $\binom{c_x}{k}$と$\operatorname{dp}[x+1 ... N]$の積を掛けて求まることになる。$k=0$から$f$を求めていくとして、$\operatorname{dp}$の末尾から$k$が増えていくので、$k$の昇順、タイブレークは$x$の降順に$f(x, k)$を求めつつ$\operatorname{dp}$を更新していくと、一回の更新が${O}(\log N)$でできる。