はまやんはまやんはまやん

hamayanhamayan's blog

キャンディーとN人の子供 [ARC059 : E]

問題

http://arc059.contest.atcoder.jp/tasks/arc059_c

(複雑なのでリンク先を見ましょう)
(結構分かりにくい)

1 <= N, C, Ai, Bi <= 400

帰納的考察(Editorialとかkmjpさんとかmayokoさんとか)

1. さっぱり分からん
2. 部分点解法がまずさっぱり分からん

――壁――

3. DPを使用するという発想
4. こういう問題でDPが使えるというのは典型なの?(トップ陣解くの早すぎ)
5. 「10^9+7で割ったあまり」という部分がDPっぽい感じ?
6. すごい人は、どこを見てDPだと思ったんだろう
7. 解説通りのDPを書いて通しました

dp[i][j] = x1からxiまでの変数を使って次数がjとなる単項式の値の和
dp[i + 1][j] = sum { dp[i][j-k]*xi^k } (k = 0...j)
ちょっと分かりにくいが、dp[i][j-k]が(j-k)次の集まりでxiがk次だから、かけるとj次ができる的な考え方するといい

8. これで部分点とかヤバイ
9. 満点では、ここから更に等式変形をして頑張らなくては行けない(マジでプロどうやってんの??)
10. 等式変形をすると、xi^kをAi^k+(Ai+1)^k+...+Bi^kに変更すれば良いと分かる
11. この値は前処理として計算しておく
12. これで通る

実装

http://arc059.contest.atcoder.jp/submissions/841525

typedef long long ll;
ll MOD = 1000000007;
int N, C;
int A[400], B[400];
ll dp[401][401];
ll memo[401][401];
//-----------------------------------------------------------------
int main() {
	cin >> N >> C;
	rep(i, 0, N) scanf("%d", &A[i]);
	rep(i, 0, N) scanf("%d", &B[i]);
 
	rep(i, 0, N) rep(k, A[i], B[i] + 1) {
		ll p = 1;
		rep(j, 0, C + 1) {
			memo[i][j] = (memo[i][j] + p) % MOD;
			p = (p * k) % MOD;
		}
	}
 
	dp[0][0] = 1;
	rep(i, 0, N) rep(j, 0, C+1) rep(k, 0, j+1) {
		dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - k] * memo[i][k]) % MOD;
	}
	cout << dp[N][C] << endl;
}