kmjp's blog

競技プログラミング参加記です

AtCoder ARC #059 : E - キャンディーとN人の子供 / Children and Candies

ARC

無駄に難しく考えてしまったけどそう難しくなかった。
http://arc059.contest.atcoder.jp/tasks/arc059_c

問題

N人の幼児がそれぞれパラメータX[i]を持つとする。
F(X[0],X[1],....,X[N-1])とは、N人の幼児に飴を計C個配るときの各パターンにおいて、各幼児がa[i]個もらったとき、 \prod_i {X_i}^{a_i}の総和とする。

幼児のパラメータのふり幅がA[i]≦X[i]≦B[i]である場合のFの総和、すなわち \displaystyle \sum_{X_0=A_0}^{B_0}\sum_{X_1=A_1}^{B_1}...\sum_{X_{N-1}=A_{N-1}}^{B_{N-1}} F(X_0,...,X_{N-1})を求めよ。

解法

シンプルにA[i]=B[i]の場合を考えよう。
dp(k,n) := k番目までの幼児にn個の飴を配った場合、X[i]^a[i]の積の総和
とする。(k-1)番目までの幼児に(n-m)個の飴を配り、k番目の幼児にm個の飴を配ると考えると、
dp(k,n) += dp(k-1,n-m)*(A[i]^m)
のDPで解くことができる。これはO(N^3)のDP。

次にA[i]!=B[i]の場合だが、これは単に以下のようにDPの際の係数を変えるだけ。
dp(k,n) += dp(k-1,n-m)*(A[i]^m+(A[i]+1)^m+...+B[i]^m)
後半の和の部分を毎回計算するとO(N^4)になってTLEするので、前処理で累積和を取るなどしておこう。

int N,C;
int A[404],B[404];
ll mo=1000000007;
ll ppow[404][404];
ll ppowS[404][404];

ll dp[404][404];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	
	ppow[0][0]=1;
	for(i=1;i<=400;i++) {
		ppow[i][0]=1;
		FOR(j,400) ppow[i][j+1]=ppow[i][j]*i%mo;
	}
	FOR(i,401) FOR(j,401)  (ppowS[j+1][i]=ppowS[j][i]+ppow[j][i])%=mo;
	
	
	dp[0][0]=1;
	FOR(i,N) FOR(x,C+1) for(y=0;x+y<=C;y++) {
		ll p=(ppowS[B[i]+1][y]-ppowS[A[i]][y])%mo;
		if(p<0) p+=mo;
		(dp[i+1][x+y] += dp[i][x] * p) %= mo;
	}
	cout<<dp[N][C]<<endl;
	
}

まとめ

もっと複雑な式変形がいるかと身構えて先にFの部分点取りに行ったけど、必要なかったな。