$1$ 回に移動できるマスの数の集合 $S$ が $k$ 個の区間の和集合として与えられたとき，マス $1$ からマス $n$ までの移動の仕方が何通りあるか求める．($k \leq 10, n \leq 2 \times 10 ^ 5$)
解説
$n$ までの移動の仕方が $\mathrm{DP}[n]$ 通りとすると，
$$
\mathrm{DP}[n] = \sum _ {s \in S} \mathrm{DP}[n - s]
$$
が成り立つから，各 $i = 0, \ldots, n - 1$ と 各 $s \in S$ について $\mathrm{DP}[i + s]$ に $\mathrm{DP}[i]$ を足していけば答えが求められるが，これは計算量が $O(n ^ 2)$ なので高速化する．
一般に，配列 $A$ の「区間 $[\ell, r]$ に $x$ を足す操作」を何回か繰り返すとき，$A[\ell]$ に $x$，$A[r + 1]$ に $-x$ を足して，最後に累積和をとるという方法がある．
これを応用して，最初に $\mathrm{DP}[0] = 1$, $\mathrm{DP}[1] = -1$ とおいて，各 $i = 0, \ldots, n - 1$ ごとに各区間 $[\ell,r]$ について $\mathrm{DP}[i + \ell]$ に $+ \mathrm{DP}[i]$， $\mathrm{DP}[i + r + 1]$ に $- \mathrm{DP}[i]$ を行い，$\mathrm{DP}[i + 1]$ をそこまでの累積和になるようにすることで，$O(n k)$ で計算できる．
実装
Submission #16925012 - AtCoder Beginner Contest 179
p = 998244353 n, k = map(int, input().split()) LR = [tuple(map(int, input().split())) for _ in range(k)] DP = [0] * (2 * n + 1) DP[0] = 1 DP[1] = -1 for i in range(n): for l, r in LR: DP[i + l] += DP[i] DP[i + r + 1] -= DP[i] DP[i + 1] += DP[i] DP[i + 1] %= p print(DP[n - 1])
