最酷的排列

idea,sol,data,std from Kubic

别急。

下面是 Rainbow_sjy 代更。

首先我们只需要考虑相邻元素的交换。

从后往前扫，最终位置 $i$ 的数不可能比 $i$ 和 $i$ 后面的数更小。

用小根堆维护后缀中的数，碰到酷的位置，就弹出最小的计入答案。这个答案是下界，而且是可以构造得到的。

里外一致

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}(\genfrac{}{}{0ex}{}{2(K-i)}{K-i})[x^i]G(x)$。

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

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

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

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

二维抄袭检测

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

$n\le 2$

一个点只有两个出边。

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

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

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

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

$n\le 3$

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

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

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

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

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

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

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

$n\le 4$

贪心还有救吗？ $$\begin{gathered} S=\text{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx} \\ \begin{array}{rl}T=& \mathtt{\text{xxxxxxxxxxxxxxxxxx}}\mathtt{\text{aaaaaa}}\\ & \mathtt{\text{a}}\mathtt{\text{x}}\mathtt{\text{aa}}\mathtt{\text{x}}\mathtt{\text{a}}\mathtt{\text{x}}\mathtt{\text{a}}\mathtt{\text{x}}\mathtt{\text{a}}\mathtt{\text{x}}\mathtt{\text{a}}\mathtt{\text{x}}\mathtt{\text{a}}\mathtt{\text{x}}\mathtt{\text{a}}\mathtt{\text{x}}\mathtt{\text{aaaaaaa}}\\ & \mathtt{\text{a}}\mathtt{\text{x}}\mathtt{\text{aaaaaaaaaaaaaaaaaaaaaa}}\\ & \mathtt{\text{a}}\mathtt{\text{xxxxxxxxxxxxxxxxxxxxxxx}}\end{array} \end{gathered}$$

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

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

因为考虑所有从第二行转移到第三行的列，如果这一列的第一行无法到达，那么可以被走完第一行再接 $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\le 1000$

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

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

$L,m,q\le {10}^4$

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

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

$n\le 7$

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

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

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

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

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

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

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

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

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

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

$n\le 10$

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

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

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

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

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

谢罪

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