問題
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; }