ARC 059 E - キャンディーとN人の子供

• 問題
• AC

部分点のケースについて考える。$x_i$が一定の場合、
$g(k, y) := \sum_{a_1 + ... + a_N = y} \prod_{i=1}^k x_i^{a_i}$

とすると答えは$g(N, C)$で、漸化式は

$g(k, y) = g(k-1, y) + x_k g(k-1, y-1) + ... + x_k^y g(k-1, 0)$

$g(0, 0) = 1$

$g(0, y) = 0 \qquad (y \neq 0)$

と書ける。DPすれば計算量は${\mathcal O}(NC^2)$。

元の制約についてもだいたい同じように解ける。

$h(k, y) := \sum_{x_1 = A_1}^{B_1} \sum_{x_2 = A_2}^{B_2} ... \sum_{x_N = A_N}^{B_N} \sum_{a_1 + ... + a_N = y} \prod_{i=1}^k x_i^{a_i}$

とするとやはり答えは$h(N, C)$で、

$\begin{aligned} h(k, y) & := \sum_{a_1 + ... + a_N = y} \sum_{x_1 = A_1}^{B_1} \sum_{x_2 = A_2}^{B_2} ... \sum_{x_N = A_N}^{B_N} \prod_{i=1}^k x_i^{a_i} \\ & := \sum_{a_1 + ... + a_N = y} \Bigl( \sum_{x_1 = A_1}^{B_1} x_1^{a_1} \Bigr) \Bigl( \sum_{x_2 = A_2}^{B_2}x_2^{a_2} \Bigr) ... \Bigl( \sum_{x_N = A_N}^{B_N}x_N^{a_N} \Bigr) \end{aligned}$

だから、漸化式は

$h(k, y) = h(k-1, y) + \Bigl( \sum_{x_k = A_k}^{B_k} x_k \Bigr) h(k-1, y-1) + ... + \Bigl( \sum_{x_k = A_k}^{B_k} x_k^y \Bigr) h(k-1, 0)$

となって、やはりDPすれば計算量は${\mathcal O}(NC^2)$。