ABC179D - Leaping Tak

$\mathrm{dp}$で考える場合，

• $\mathrm{dp}$を中心に考えると，「貰うDP + 累積和」になり，
• 累積和（階差）を中心に考えると，「配るDP + 階差 (いもす法)」になる

ということだと思う．

貰うDP + 累積和

AtCoder Beginner Contest 179 - YouTubeの方法．
添字がややこしい．

考え方

貰うDPで，$1\sim N$の順にマスを見ていく（$\mathrm{dp}[i] = i$マス目に行く方法の数）．答えは$\mathrm{dp}[N]$．

$[L_{j}, R_{j}]$の$\mathrm{dp}[i]$への寄与は，

\begin{aligned}
\mathrm{dp}[i]
&= \mathrm{dp}[i] \\
&\quad
+ \sum_{k = i - R_{j}}^{i - L_{j}} \mathrm{dp}[k]
\end{aligned}

である．

よって，$i$について考えているときに，$i-1$以下の累積和

\begin{aligned}
\mathrm{acc} [l]
= \sum_{k=1}^{l} \mathrm{dp}[k]
\end{aligned}

が既知であれば，$\mathrm{dp}[i]$は$O(K)$の計算で求められる．

以上より，$O(NK)$で解けた．

回答例

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]
mod = 998244353

dp = [0] * (N + 1)
acc = [0] * (N + 1)
dp[1] = 1
acc[1] = 1
for i in range(2, N + 1):
  for l, r in LR:
    l2 = max(0, i - r - 1)
    r2 = max(0, i - l)
    dp[i] += acc[r2] - acc[l2]
    dp[i] %= mod
  acc[i] = acc[i - 1] + dp[i]
  acc[i] %= mod
      
print(dp[N])

配るDP + 階差 (いもす法?)

Editorial - AtCoder Beginner Contest 179の方法．こっちのほうが，添字がややこしくない．

考え方

多分，いもす法．

配るDPで，$1\sim N$の順にマスを見ていく（$\mathrm{dp}[i] = i$マス目に行く方法の数）．答えは$\mathrm{dp}[N]$．

階差を$\mathrm{diff}[i] = \mathrm{dp}[i] - \mathrm{dp}[i-1]$とすれば，

• $\mathrm{diff}[i + 1]$は，$i$番目までの情報（$\mathrm{dp}[1]\sim \mathrm{dp}[i], \mathrm{diff}[1] \sim \mathrm{diff}[i]$）で決まる．
• 各ステップ$i$で，$ \mathrm{dp}[i] = \mathrm{dp}[i-1] + \mathrm{diff}[i]$で計算できる．

回答例

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]
mod = 998244353

dp = [0] * (N + 1)
diff = [0] * (N + 1)
dp[1] = 1
diff[1] = 1
diff[2] = -1
for i in range(1, N):
  for l, r in LR:
    if i + l <= N:
      diff[i + l] += dp[i]
      diff[i + l] %= mod
    if i + r + 1 <= N:
      diff[i + r + 1] -= dp[i]
      diff[i + r + 1] %= mod
  dp[i + 1] = dp[i] + diff[i + 1]
  dp[i + 1] %= mod

print(dp[N])