DOJ Beginner Contest 12 E - Shirogane Wants to Sing
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 12
- 問題
- E - Shirogane Wants to Sing
長さ の非負整数列 が与えられます。次の条件をすべて満たす長さ の非負整数列 の個数を で割った余りを求める問題です。
- 。
- すべての について 。
- 。
制約は 、、、 です。
を前から 1 つずつ決めていく DP をします。次の値を決めるのに必要なのは、直前の値 と、それまでの誤差の合計だけです。そこで
とします。 は だけが です( なら答えは です)。 から、 を満たす各 について、 なら に足します。答えは の値の総和です。
のとりうる範囲は有限です。 なので、 です。よって は 以上 以下だけを考えれば十分です。
計算量は で、最大でも 回程度です。
Python
MOD = 10**9 + 7N, K, E = map(int, input().split())A = list(map(int, input().split()))if A[0] > E: print(0) exit(0)M = max(A) + Edp = [[0 for i in range(M + 1)] for j in range(E + 1)]dp[A[0]][0] = 1for a in A[1:]: ndp = [[0 for i in range(M + 1)] for j in range(E + 1)] for i in range(E + 1): for j in range(M + 1): for k in range(j - K, j + K + 1): if k not in range(M + 1): continue if abs(a - k) + i > E: continue ndp[abs(a - k) + i][k] += dp[i][j] ndp[abs(a - k) + i][k] %= MOD dp = ndpprint(sum(sum(a) % MOD for a in dp) % MOD)dp[i][j] が、誤差の合計が i で直前の値が j である数列の個数です。k が次の値 の候補で、範囲 から外れるものと、誤差の合計が を超えるものを飛ばしています。