ARC059-E Children and Candiesの解説です。公式解説が少しわかりにくい気がしたので、是非こちらも参考にしてください。
問題概要
$N$ 人の子供たちに $C$ 個のキャンディーを、非負整数個づつ配る。（つまり、１つも配らない子供がいても良い。）
それぞれの子供たちは値 $x_i$ を持っており、子供 $i$ にキャンディーを $k$ 個配った時、子供の「うれしさ」は $x_i^k$ となる。幼稚園の活発度は、子供たちの嬉しさの積として計算される。 $x_i$ が $A_i$ から $B_i$ までの値をとる時、ありうる全ての $x_i$ とキャンディーの配り方について、活発度の総和を求めよ。
部分点解法
この問題は、満点解法も部分点解法と同様な発想をするので、部分点解法から解説します。
部分点では、$A_i=B_i$ から、$x_i$ の値が一意に定まっていることがわかります。
この問題は、次のようなDPで簡単に解けます。
定義:dp[$i$][$j$]= $i$ 番目までの子供たちに $j$ 個のキャンディーを配った時の、そこまでのうれしさの積としてありうるものの総和
初期値:dp[$0$][$0$]=$1$
遷移:dp[$i+1$][$j+k$]+=dp[$i$][$j$]*$x_i^k$
答え:dp[$N$][$N$]
dp[$i+1$][$j+k$]への遷移を計算する時、$i$,$j$以外の情報は必要なく、総和としてまとめて計算していいことさえわかれば、このDPが成立していることがわかると思います。
計算量は $O(NC)$ です。
ここまでは水色程度の人には少し厳しいかもしれませんが、思いついて欲しいところです。
満点解法
満点の制約では、$x_i$ の範囲が最大 $400$ なので、上のDPを全ての $x_i$ の組み合わせに対して行うと計算量が爆発します。
ここで、キャンディーの配り方を固定し、子供 $i$ に配る数を $c_i$ としてみます。
ここで、全ての $x_i$ の組み合わせについての活発度の総和を求めることを考えます。
実はこれの値は、次の値と等しいです。
$\prod_{i=1}^N \sum_{j=A_i}^{B_i} j^{c_i}$
なぜでしょうか。とりあえず可視化してわかりやすくしましょう。
$(A_1^{c_1}+(A_1+1)^{c_1} \cdots B_1^{c_1})(A_2^{c_2}+(A_2+1)^{c_2} \cdots B_2^{c_1}) \cdots(A_N^{c_N}+(A_N+1)^{c_N} \cdots B_N^{c_N})$
これを展開すると、全ての $x_i$ の組み合わせが1度ずつ現れるので、全ての組み合わせについての活発度の総和となります。
このような式変形はあまり珍しいものではないため、多少数学ができればわかると思います。
こう考えると、部分点のDPの遷移を少し変えるだけで満点解法へと拡張することができます。
つまり、dp[$i+1$][$j+k$]+=dp[$i$][$j$]*$(\sum_{l=A_i}^{B_i} l^k)$
とすれば良いです。
このシグマの部分をいちいち計算すると計算量は$O(NC\ max(B_i))$ となり、間に合いません。
そこで、ありうる全ての $l$ と $k$ について、$1^k$ から $l^k$ までの和を前計算で求めておけば、引き算によってシグマの部分の値が $O(1)$ で求まります。
よって、前計算に $O(C\ max(B_i))$,DPパートに $O(NC)$ かかり、合計 $O(C(max(B_i)+N))$ でこの問題が解けました。
おわりに
ABCやAGCには出なさそうな雰囲気ですが、ARCや企業コンにバンバン出そうな雰囲気をした問題なので、企業コンでレート爆上げしたい人はちゃんと押さえておきましょう。
ありがとうございました。