問題概要
$X$ 軸上に住むことを考える（原文参照＞＜；）．今，$x = 1$ の地点にいて，次の方法で移動することができる．
$K$ 個の区間 $[ L_i, R_i ]$ ($0 \leq i \leq K$) が与えられる．この区間の和集合*1 $S = \cup_i [ L_i, R_i ]$ を考える．座標 $i$ からは $d \in S$ について，$i + d$ へ移動できる．
座標 $N$ に到達する方法は何通りあるか？ $\pmod { 998244353 }$ で求めよ
制約
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq K \leq \min( N, 10 )$
- その他いい感じの制約
解法 1
次のように状態をとる動的計画法を考えます．
- $\mathit{ dp }_i$ := 座標 $i$ に移動する方法の総数
状態 $\mathit{ dp }_i$ からの遷移は，愚直に実装すると次のようになります．
- 各 $d \in S$ について，$\mathit{ dp }_i$ の値を $\mathit{ dp }_{ i + d }$ に足し込む
この DP は，各区間の長さが十分長い場合に $\Theta( N^2 )$ 時間となることが分かります．
しかしよく見ると，各区間に対して一様に値を足し込んでいます．この操作は，いわゆる「一様加算」ができる segment tree を用いると $O( \log N )$ 時間で処理できます．よって，DP 配列を普通の配列ではなく segment tree で実装することで全体を $O( N K\log N )$ 時間にでき，間に合わせることができます．
解法 2
解法 1 と同様の DP を考えます．ただし今度は普通の配列上で工夫をします．
区間加算を処理した結果を得る手法として いもす法 が知られています．今回の DP もある意味区間へ加算とその処理結果が欲しいので，いもす法の応用で解くことができます．
イメージとしては，上記の DP といもす法を同時に並行して進めていく感じになります．具体的には，配列を 2 パートに分けて，「ある位置より左はいもす法での累積和が取られた後・右側では累積和がとられる前」とし，DP で着目している位置を分割点とします．具体的な値で言うと，
- $\mathit{ dp }_0 = 1$
- $\mathit{ dp }_1 = -1$
で初期化します*2．これは区間 $[ 0, 1 )$ への加算です．その後 DP を回しますが，$\mathit{ dp }_i$ からの遷移では，各 $j$ ($0 \leq j < K$) について
- $\mathit{ dp }_{ i + L_j }$ に $\mathit{ dp }_i$ を足し込む
- $\mathit{ dp }_{ i + R_j + 1 }$ に $-\mathit{ dp }_i$ を足し込む
として区間を処理します．その後，
- $\mathit{ dp }_{ i + 1 }$ に $\mathit{ dp }_i$ の値を足し込む
ことをしていもす法における累積和を 1 進めます．最後に $\mathit{ dp }_{ N - 1 }$ を読むと答えが入っています．
この方法では，各位置からの遷移は $\Theta( K )$ 通りで，ひとつあたりは $O( 1 )$ 時間で処理できるので，全体では $\Theta( NK )$ 時間になります．
コード
// segment tree, range add, sum class SegmentTreeRAS; // SegmentTreeRAS( VI src ) // add( [ a, b ), x ) // sum( [ a, b ) ) int main() { IN( int, N, K ); VI L( K ), R( K ); REP( i, K ) { cin >> L[i] >> R[i]; } SegmentTreeRAS segtree( 2 * N + 2 ); segtree.add( 0, 1, 1 ); REP( i, N - 1 ) { REP( j, K ) { const int l = i + L[j]; const int r = i + R[j]; segtree.add( l, r + 1, segtree.sum( i, i + 1 ) ); } } cout << segtree.sum( N - 1, N ) << endl; return 0; }
constexpr int MOD = 998244353; int main() { IN( int, N, K ); VI L( K ), R( K ); REP( i, N ) { cin >> L[i] >> R[i]; } static int dp[ 1 << 20 ]; dp[0] = 1; dp[1] = MOD - 1; REP( i, N ) { REP( j, K ) { ( dp[ i + L[j] ] += dp[i] ) %= MOD; ( dp[ i + R[j] + 1 ] += MOD - dp[i] ) %= MOD; } ( dp[ i + 1 ] += dp[i] ) %= MOD; } cout << dp[ N - 1 ] << endl; return 0; }
