First, the naivest solution is a Dynamic Programming (DP) where \(f_i\) := the number of ways to go to Cell \(i\), and check all the possible move for each \(i\), but this needs a time complexity of \(\mathrm{O}(N^2)\).

Let us consider optimizing by making use of the fact that the ways of moving can be written as a sum of small number of segments (\(S = \cup [l_j, r_j]\)). This can be solved either in so-called “distributing DP” or “receiving DP.” This time, we will explain based on distributing DP.

Assume that we have already obtained the values until \(f_i\). When transiting from \(i\), for all \(d \in S\), we want to add \(f_i\) to \(f_{i+d}\).

Here, we want to use the fact that the difference of neighboring values of \(f\) changes at \(O(K)\) positions. Let \(a_i = f_{i} - f_{i-1}\), then this can be optimized by performing the operations of \(a_{i + l_j} := a_{i + l_j} + f_i, a_{i + r_j + 1} := a_{i + r_j + 1} - f_i\) for each \(j\), and then restore \(f\) by \(f_i = f_{i-1} + a_i\).

The total time complexity is \(\mathrm{O}(KN)\).

Note that it is known that this problem can be solved in a total of \(\mathrm{O}(N \log N)\) time even when the transitions cannot be written as a sum of small number of segments.

Sammple Code (C++)