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)$ 也通过了。