2019年10月8日火曜日

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

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

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

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

g(k,y)=g(k1,y)+xkg(k1,y1)+...+xkyg(k1,0)g(k, y) = g(k-1, y) + x_k g(k-1, y-1) + ... + x_k^y g(k-1, 0)

g(0,0)=1g(0, 0) = 1

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

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

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

h(k,y):=x1=A1B1x2=A2B2...xN=ANBNa1+...+aN=yi=1kxiaih(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)h(N, C)で、

h(k,y):=a1+...+aN=yx1=A1B1x2=A2B2...xN=ANBNi=1kxiai:=a1+...+aN=y(x1=A1B1x1a1)(x2=A2B2x2a2)...(xN=ANBNxNaN)\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(k1,y)+(xk=AkBkxk)h(k1,y1)+...+(xk=AkBkxky)h(k1,0)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すれば計算量はO(NC2){\mathcal O}(NC^2)