D1T1

idea,sol,data,std from kubic

别急。

D1T2

idea from cmk666，solution from zjy0001。

记区间 $[l,r]$ 中颜色 $i$ 出现 $c_i(c_i>0)$ 次，如果 $i$ 只出现在 $S$ 中，那么有 $1$ 种选择方法，如果只出现在 $U/S$ 中，那么有 $1$ 种选择方法，否则有 $2^{c_i}-2$ 种选择方法。

考虑构造形式幂级数 $F_i(x)=(x-1)^2+2^{c_i}x,F(x)=\prod_i F_i(x)$ ,如果有 $K$ 种不同的颜色在区间 $[l,r]$ 中出现，那么答案就是 $[x^K]F(x)$。

考虑记 $y=(x-1)^2$ 那么 $F(x)$ 每一项的指数和是固定的 $K$，于是我们可以设 $G_i(x)=1+2^{c_i}x$，求出 $G(x)=\prod_i G_i(x)$，那么答案就是 $[x^K]\sum_i(x-1)^{2(K-i)}x^i[x^i]G(x)=\sum_i(-1)^{K-i}\binom{2(K-i)}{K-i}[x^i]G(x)$。

接下来观察模数的性质，因为$G_i(x)=1+2^{c_i}x,c_i>0$，所以有 $\forall i\ge 64,[x^i]G(x)\equiv 0\pmod{2^{64}}$，于是我们只需要求出 $G$ 的前 $64$ 项即可。

对于 $c_i\ge 64$，我们不用关心，因为 $G_i(x)\equiv 1\pmod{2^{64}}$，对 $G$ 的求解没有影响。

否则，对于 $1\le k\le 63$，依次统计出 $d_k=\sum_i[c_i=k]$，于是 $G(x)=\prod_{k=1}^{63} (1+2^kx)^{d_k}$，容易用组合数预处理出 $(1+2^kx)^{d_k}$ 的每一项系数，并且对于每一个 $k$，其只有前 $\lfloor \dfrac{63}{k}\rfloor$ 的值在模意义下不为 $0$，如果我们从大到小依次枚举 $k$ 乘起来，它依然保持这个性质，于是单次计算 $G(x)$ 的复杂度就是 $\Theta(\log^2 P)$ 的了。

如果用扫描线配合树状数组求出 $d_k$，那么总时间复杂度就是 $\Theta((n+q)\log n\log P+q\log^2 P)$ 的。

D1T3

idea,data,std from unputdownable, solution from unputdownable,zhoukangyang

$n \le 2$

一个点只有两个出边。

如果两者字符不一样，那么直接走对应字符的出边就行。

难处理的是两条出边字符相等的情况。

但是 $n \leq 2$，注意到向右走一定不劣，所以贪心先匹配第一行，然后再往第二行匹配即可。

总复杂度 $O(L+nm+q\log m)$，也可以做到单组查询 $O(1)$。

$n \leq 3$

贪心失效了！真的失效了吗？

考虑我们的贪心什么时候会挂。 $$ S=\text{xxxxxxxxxxxxxxxxxxxxx}\\ \\ \begin{aligned} T=\ &\color{red}\texttt{xxxxxxxxxxxx}\color{black}\texttt{aaaaa}\\ &\color{blue}\texttt{aaaax}\color{black}\texttt{aaaaaaaaaaaa}\\ &\texttt{aaaa}\color{blue}\texttt{xxxxxxxxxxx}\color{black}\texttt{aa}\\ \end{aligned} $$ 考虑选择一个位置提前往下拐。

注意到如果在蓝色分支之前就往下拐，一定不比蓝色优，否则蓝色一定能接到那个路径上去。

所以应该选择最后一个能往下拐的位置往下拐，然后就是 $n=2$ 的部分了。

注意到能往下拐的位置一定满足 $T_{2,x}=T_{1,x+1}$，或者在末尾，而这个是好维护的

记得在两种贪心中取较大的一个。

总复杂度仍是 $O(L+nm+q\log m)$，也可以做到单组查询 $O(1)$。

$n \leq 4$

贪心还有救吗？ $$ S=\text{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}\\ \\ \begin{aligned} T=\ &\color{red}\texttt{xxxxxxxxxxxxxxxxxx}\color{}\texttt{aaaaaa}\\ &\texttt{a}\color{green}\texttt{x}\color{}\texttt{aa}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{black}\texttt{aaaaaaa}\\ &\texttt{a}\color{green}\texttt{x}\color{}\texttt{aaaaaaaaaaaaaaaaaaaaaa}\\ &\texttt{a}\color{green}\texttt{xxxxxxxxxxxxxxxxxxxxxxx}\\ \end{aligned} $$

这样子可以把上述贪心卡死。

但是如果能找到一个直达第三排的位置，从那个位置往下拐贪一下，就还有救。

因为考虑所有从第二行转移到第三行的列，如果这一列的第一行无法到达，那么可以被走完第一行再接 $n=3$ 的贪心；

而当我们找到一个能直达第三行的位置，和 $n=3$ 的情况就差不多了，可以证明这是最优的决策之一。

观察到能到第三排的位置应该满足 $T_{2,x}=T_{1,x+1}，T_{3,x}=T_{1,x+2}$；或者 $x$ 在第一行贪心匹配部分（上图红色）末尾两个字符（需要特判）。

将走完第一行再接 $n=3$；第一行走到剩下一个再接 $n=3$；选择最后一个能往下拐的位置往下拐；找到最后一个能直达第三行的位置往下拐四种贪心拼起来即可通过 $n=4$。

总复杂度仍是 $O(L+nm+q\log m)$，也可以做到单组查询 $O(1)$。

$L,m,q \leq 1000$

对于询问暴力跑一个朴素的 DP，记 $f_{i,j}$ 表示能否走到 $(i,j)$ 这个点，单次询问复杂度 $O(nm)$，

总复杂度 $O(L+nm+qnm)$。

$L,m,q \leq 10^4$

注意到 DP 状态只有 $01$，直接压位用位运算做 DP，单组询问复杂度 $O(m)$；

总复杂度 $O(L+nm\sum+qm)$。

$n \leq 7$

贪心彻底没救了，因为此时路径的形态会变得相当复杂。

注意到 $n$ 很小，考虑想办法维护上述动态 DP。

首先将矩阵转换为斜矩阵以方便理解（第 $i$ 行向右平移 $i-1$ 个字符），这样每一步是向右或者向右下走，即第 $i$ 步一定走到第 $i$ 列。

维护 DP，第 $i$ 列的状态只和第 $i-1$ 列的状态以及需要匹配的字符有关。

难点在于转移矩阵会随着询问的字符串而改变。

想办法固定每个位置的转移矩阵。

注意到如果先贪心在第一行匹配，那么在和第一行匹配上的这个区间内，转移矩阵是固定的。

直接动态 DP 维护此时的 DP 状态；如果下面的行已经没有可达的位置了，那么贪心匹配第一行一定是最优的；否则跳到下方第一个可以到达的行，然后递归。

预处理动态 DP 矩阵，查询时只需要做至多 $n$ 遍向量乘区间的转移矩阵。

视实现的不同复杂度大约 $O(L \log L+n^3m\log m+qn^3)$。

$n \leq 10$

注意到矩阵很小，可以压位，单次矩乘 $O(n^2)$。

上猫树，注意到每次乘的是单个转移矩阵，而不是若干转移矩阵的积，其中非 $0$ 元素只有 $O(n)$ 个。

这样预处理时单次矩乘 $O(n)$。

复杂度 $O(L \log L+n^2m \log m+qn^2)$。

由于实测时间瓶颈在 $SA$ 预处理上，所以即使你的询问多一个 $n$ 或者多一只 $\log$，如果卡常较为精细也能通过。

谢罪

部分乱搞获得了 $84$，复杂度错误的 $O(m2^{\frac n 2})$ 以及 $O(m2^n)$ 也通过了。