halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ARC059E - Children and Candies / キャンディーとN人の子供

競プロ 今日の精進 ARC 黄Diff

毎日格上の問題を倒すやつの50日目です。*1

問題リンク*2

atcoder.jp

問題概要

N 人の子供がいるよ。

i 人目のはしゃぎ度を x_i 、i 人目に配るキャンディーの量を a_i として、幼稚園の活発度を \prod_{i=1}^{N} x_i^{a_i} とするよ。

i 人目のはしゃぎ度が A_i から B_i を動き、C 個のキャンディーを配るとき、すべての方法での幼稚園の活発度の総和を求めてね。

解法

求めるものは [x^C]\prod_{i=1}^{N}\frac{1}{1-A_ix}+\frac{1}{1-(A_i+1)x}+\dots+\frac{1}{1-B_ix} と解釈することができます。

すると、それぞれに対して和を計算するだけでよいことがわかります。

そのため、事前に累積和を計算してから3乗のDP的な感じで計算すれば終わりです。

提出コード

MOD=10**9+7
N,C=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
power=[[0]*(C+1) for i in range(401)]
for i in range(1,401):
    for j in range(C+1):
        power[i][j]=power[i-1][j]+pow(i,j,MOD)
        power[i][j]%MOD
dp=[[0]*(C+1) for i in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(C+1):
        for k in range(j+1):
            dp[i+1][j]+=dp[i][j-k]*(power[B[i]][k]-power[A[i]-1][k])
            dp[i+1][j]%=MOD
print(dp[-1][-1]%MOD)

Submission #47400366 - AtCoder Regular Contest 059

感想

FPSぽくはないけど少しは見通しがよくなったからセーフ

*1:もとい、FPSウィークの5日目です。たぶんこれメインでやるのは明日まで…

*2:今回はFPSあんま関係ないかもだけど式変形要素はあるので