题解

思路

令 $C_{N+1}=0$，并令 $C_i=(C_{i+1}+B^{N-i}A_i)\bmod P$。

做法

由于 $B$ 在模 $P$ 下可逆，$A$ 与 $C_1,\ldots,C_N$ 一一对应；区间哈希可写成 $B^{R-N}(C_L-C_{R+1})$，所以它非零恰好等价于 $C_L\ne C_{R+1}$。于是每个区间 $(L,R)$ 对应图上的边 $(L,R+1)$，问题转化为判断这个 $N+1$ 点图能否用不超过 $P$ 种颜色正确染色。

预处理每个顶点子集是否为独立集。令 $dp[S]$ 为诱导子图 $S$ 的最小色数，若 $S$ 独立则为一，否则枚举包含固定最低位顶点的独立子集 $T\subseteq S$，转移 $dp[S]=\min(dp[S\setminus T]+1)$。

复杂度

固定一位避免重复枚举同一划分，复杂度为 $O(3^{N+1})$，空间复杂度为 $O(2^{N+1})$。