まず、素朴な解法としては、\(f_i\) := マス \(i\) まで移動する方法の個数と置いて、各場所 \(i\) についてすべての移動を試す動的計画法が考えられますが、時間計算量 \(\mathrm{O}(N^2)\) となります。

移動方法が少ない区間の和 (\(S = \cup [l_j, r_j]\))として書けることを利用した高速化を考えます。いわゆる配る DP, 貰う DP のどちらでも解くことができますが、今回は配る DP に基づいて説明します。

今、\(f_i\) までの値が正しく求まっているとしましょう。\(i\) から遷移するとき、すべての \(d \in S\) について \(f_{i+d}\) に \(f_i\) を足す操作を行います。

このとき \(f\) の隣同士の差が \(O(K)\) 箇所でしか変化しないことを利用したいです。これは \(a_i = f_{i} - f_{i-1}\) と置いて各 \(j\) について \(a_{i + l_j} := a_{i + l_j} + f_i, a_{i + r_j + 1} := a_{i + r_j + 1} - f_i\) という操作を行い、\(f_i = f_{i-1} + a_i\) で \(f\) を復元することで高速化できます。

時間計算量は \(\mathrm{O}(KN)\) です。

なお、遷移が少ない区間の和で表わせなくともこの制約の下で \(\mathrm{O}(N \log N)\) で解けることが知られています。

実装例(C++)