Problem:


D : Hopping Hearts / こころぴょんぴょん

問題文

N 羽のうさぎが長さ L&minus;1 の平均台の上にいる。 i 番目のうさぎの初期位置は整数 x_iであり、 0 ≤ x_{i} \lt x_{i+1} ≤ L&minus;1 を満たす。座標は右に進むほど大きくなる。任意の i 番目のうさぎは、任意の回数だけ、ちょうど距離 a_i だけ右方向にジャンプ(すなわち、x_i から x_i+a_i へ移動)することができる。ただし別のうさぎを飛び越えること、&minus;1 以下または L 以上の位置に入ることはできない。また、同時にジャンプしていられるのは高々 1 羽であり、ある座標に存在できるうさぎの数も高々 1 羽である。

初期状態から始めてジャンプを任意の回数繰り返したあとの x_{0}, …, x_{N&minus;1} の状態として、あり得るものは何通りあるか。1\,000\,000\,007 で割った余りで求めよ。

入力

入力は以下の形式で与えられる。

N L
x_{0} … x_{N&minus;1}
a_{0} … a_{N&minus;1}

制約

入力はすべて整数である

1 \≤ N \≤ 5\,000

N \≤ L \≤ 5\,000

0 \≤ x_{i} \lt x_{i+1} \≤ L&minus;1

0 \≤ a_{i} \≤ L&minus;1

出力

答えを1行で出力せよ。

サンプル

サンプル入力1

1 3
0
1

サンプル出力1

3

1/0でうさぎがいる/いないを表現すれば、100, 010, 001 の 3 通りである。

サンプル入力2

2 4
0 1
1 2

サンプル出力2

4

1100, 1001, 0101, 0011 の 4 通りである。

サンプル入力3

10 50
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1

サンプル出力3

272278100

二項係数 C(50,10) = 10\,272\,278\,170 であり、それを 1\,000\,000\,007 で割ったあまりは 272\,278\,100 である。



Sample input:
1 3
0
1


Sample output:
3

Submission status: Accepted

Solution code:
def main():
  MOD = 1000000007
  n, l = map(int, input().split())
  xlst = map(int, input().split())
  alst = map(int, input().split())
  can_use = []
  for x, a in zip(xlst, alst):
    if a == 0:s = {x}
    else:s = {k for k in range(x, l, a)}
    can_use.append(s)
  
  dp = [[0] * l for _ in range(n)]
  for j in range(l):
    dp[0][j] = dp[0][j - 1] + int(j in can_use[0])
  
  for i in range(1, n):
    acc = 0
    dpi = dp[i]
    dpi1 = dp[i - 1]
    st = can_use[i]
    for j in range(1, l):
      if j in st:acc = (acc + dpi1[j - 1]) % MOD
      dpi[j] = acc
  print(dp[n - 1][l - 1])

main()