\(dp[i][j] = (i,j)\) にたどり着く方法の個数という動的計画法を以下の初期値と遷移で行うことでこの問題を \(\mathrm{O}(NM)\) で解くことが出来ます。

• \(dp[1][j] =(A_k = j\) を満たす整数 \(j\) の個数\()(1 \le j \le M)\)
• \(dp[i][j] = dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1](2 \le i \le N,1 \le j \le M)\)

ただし、\(dp[i][0] = dp[i][M+1] = 0\) とします。ですが、この解法では実行制限時間に間に合いません。そこで、鏡像法というテクニックを使います。動的計画法の \(j\) の範囲を \(1 \le j \le M\) から \(0 \le j \le 2M+1\) に拡張して、以下のように遷移します。

• \(dp[1][j] =(A_k = j\) を満たす整数 \(j\) の個数\()(1 \le j \le M)\)
• \(dp[1][2M+2-j] =(-1) \times (A_k = j\) を満たす整数 \(j\) の個数\()(1 \le j \le M)\)
• \(dp[1][0] = dp[1][N+1] = 0\)
• \(dp[i][j] = dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1](2 \le i \le N,0 \le j \le 2M+1)\)

例えば、sample 2 だと以下のように遷移が行われます。

   0   2   0   1   1   0   0   0   0   0   0   0   0   0  -1  -1   0  -2
   0   2   3   2   2   1   0   0   0   0   0   0   0  -1  -2  -2  -3  -2
   0   5   7   7   5   3   1   0   0   0   0   0  -1  -3  -5  -7  -7  -5
   0  12  19  19  15   9   4   1   0   0   0  -1  -4  -9 -15 -19 -19 -12
   0  31  50  53  43  28  14   5   1   0  -1  -5 -14 -28 -43 -53 -50 -31

直観的に言うと、\(dp[i][0],dp[i][M+1]\) の部分で本来禁止されている移動を \(+,-\) で打ち消し合うことが出来ます。

このように添え字を拡張することで、遷移を多項式で表すことが出来ます。つまり、\(f_i(x) = \sum_{j=0}^{2M+1} dp[i][j] x^j\) と置くと \(f_i(x) = f_{i-1}(x) \times (x^{-1} + 1 + x)\) と表すことが出来ます。ただし、\(x\) の指数は \(\bmod\ 2M+2\) を取るものとします。(これを \(x^{2M+2} = 1\) とみなすことから、\(\bmod\ (x^{2M+2} - 1)\) と表します。)先ほどまでの動的計画法だと、\(dp[i][0],dp[i][M+1]\) が定義されておらず多項式で表すことが難しいです。

よって、\(f_N(x) = f_1(x) \times (x^{-1} + 1 + x)^{N-1} \bmod (x^{2M+2}-1)\) を求めればよいです。繰り返し二乗法を用いることで \(\mathrm{O}(M\log M \log N)\) で \(f_N(x)\) の係数を求めることが出来ます。その後、\(1 \le i \le L\) に対する \(f_N(x)\) の \(x^{B_i}\) の係数の総和を求めることでこの問題を解くことが出来ます。計算量は \(\mathrm{O}(M\log M \log N)\) です。