https://yukicoder.me/problems/no/801
解法
https://yukicoder.me/submissions/325930
dp[k][floor] := k回移動後にfloor回にいる組合せ
でDPしよう。
dp[k][???]からdp[k+1][???]を高速に更新することを考えよう。
まずは、愚直解から作る。
あるエレベータmを使うとしたときに、
dp[k+1][x] += sum{y=L[m]...R[m]}dp[k][y]
L[m]≦x≦R[m]
という遷移となることが分かる。
これを高速化したいのだが、sum{y=L[m]...R[m]}dp[k][y]の部分は慣れていると、累積和でいけるなと気づく。
しかも重要なことに、この値は、あるエレベータmによって固定の値になっている。
つまり、sumの値をdp[k + 1][L[m]], dp[k + 1][L[m]+1], ..., dp[k + 1][R[m]]に一律足していることになる。
この一律に足す操作はimos法を使えば、O(M+N)で実現できる。
移動はK回行われるので、O(K(M+N) )となり、これは間に合う。
int N, M, K, L[3010], R[3010]; mint dp[3010][3010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> K; rep(m, 0, M) { cin >> L[m] >> R[m]; } dp[0][1] = 1; rep(k, 0, K) { rep(i, 1, N + 1) dp[k][i] += dp[k][i - 1]; rep(m, 0, M) { int l = L[m], r = R[m]; mint sm = dp[k][r] - dp[k][l - 1]; dp[k + 1][l] += sm; dp[k + 1][r + 1] -= sm; } rep(i, 1, N + 1) dp[k + 1][i] += dp[k + 1][i - 1]; } cout << dp[K][N] << endl; }