\(A\) の要素は \(\text{mod }P\) を取って考えても問題ないので、以下では \(0 \leq A_i \lt P\) とします。

\(A\) を \(1\) つ取った時、以下の漸化式によって数列 \((C_1, C_2, \dots, C_{N + 1})\) を定義します。

\[ \begin{aligned} C_{N + 1} &= 0 \\ C_i &= (C_{i + 1} + B^{N - i} A_i) \bmod{P} \end{aligned} \]

このとき、実は \((A_1, A_2, \dots, A_N)\) \((0 \leq A_i \lt P)\) からなる集合と \((C_1, C_2, \dots, C_N)\) \((0 \leq C_i \lt P)\) からなる集合は一対一対応しています。なぜならば \((C_1, C_2, \dots, C_N)\) を 1 つ固定したときに

\[A_i = \left((C_i - C_{i+1}) \times B^{-(N - i)}\right) \bmod p\]

という式によって対応する \((A_1, A_2, \dots, A_N)\) を復元することができるからです。(ここで \(B^{-1}\) は \(B\) の \(\text{mod }p\) 上の逆元を意味します。)

また、\(\mathrm{hash}((A_L, A_{L+1}, \dots, A_R))\) を \(C\) を用いた表現に書き換えると次のようになります。

\[ \begin{aligned} &\mathrm{hash}((A_L, A_{L+1}, \dots, A_R)) \\ &=\left(\sum_{i=L}^R A_i B^{R-i}\right)\bmod{P} \\ &= \left(B^{R-N}\sum_{i=L}^R A_i B^{N-i}\right)\bmod{P} \\ &= B^{R-N}(C_L - C_{R + 1}) \bmod{P} \end{aligned} \]

よって \(\mathrm{hash}((A_L, A_{L+1}, \dots, A_R)) \neq 0\) という条件は \(C_L \neq C_{R + 1}\) という条件と等価です。 よって、\(C\) を用いるとこの問題は次のような問題に言い換えられます。

• \(N + 1\) 頂点 \(M\) 辺のグラフがある。辺 \(i\) は頂点 \(L_i\) と頂点 \(R_i + 1\) を結んでいる。 これから各頂点を色 \(0,1,\dots,P-1\) の \(P\) 色のどれかで塗っていく。ただし頂点 \(N+1\) はあらかじめ色 \(0\) で塗られている。 辺で結ばれた頂点同士が同じ色で塗られないように全ての頂点を塗ることは可能かを判定せよ。

この問題はまさに彩色問題です。つまり、グラフの彩色数が \(P\) 以下であるかを判定する問題に帰着することが出来ました。

グラフの彩色数を求める方法を説明します。

• グラフの頂点集合を \(V\)
• \(dp(v)\) を \(\emptyset \neq v \subseteq V\) において誘導される \(G\) の部分グラフの彩色数

としたときに、\(\emptyset \neq v \subseteq V\) において次の漸化式が成り立ちます。(\(\sqcup\) は集合の非交和)

\[dp(v) = \begin{cases} 1 & (v が独立集合) \\ \displaystyle {\min_{s \sqcup t = v, s \neq \emptyset, t \neq \emptyset}} dp(s) + dp(t) & \mathrm{otherwise} \end{cases} \]

よって、俗に部分集合 DP と呼ばれる DP によって \(G\) の彩色数を \(\mathrm{O}(3^N)\) で計算できます。
以上よりこの問題を \(\mathrm{O}(3^N)\) で解くことが出来ました。