自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:06:42，当前版本为作者最后更新于2024-11-30 15:12:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考场的思路，自认为比较清楚。

没有其它要求，一个二元限制的可能数为 $v^2$。

先只考虑一个区间，它的左右端点有限制，现在要求这个区间可行的方案数。若这个区间的长度可以放下 $x$ 个二元限制（不说长度为 $x+1$ 是因为可能会描述不清），设其方案数为 $f(x)$。

如果第一个二元限制的第一个数与左端点的数相同，那么这种情况有 $v$ 个可能的二元限制，同时下一个数也是有限制的，而剩下的方案数其实就是 $f(x-1)$，由乘法原理得此时的总方案数是 $v\times f(x-1)$。

如果第一个二元限制的第一个数与左端点的数不同，那么由于 $v\ge2$，第二个数一定有方法和第二个二元限制的第一个数不同。以此类推，后面的只要不踩中二元限制的第一个数，都一定有方法把这个区间所有数全部填上。因此，只要第一个二元限制的第一个数与左端点的数不同，剩下的二元限制随便选，都一定是有解的。剩下 $x-1$ 个二元限制方案数为 ${(v^{2})}^{(x-1)}=v^{2x-2}$，第一个由于不能和左端点相同所以是 $v\times(v-1)$，乘起来得到 $v\times(v-1)\times v^{2x-2}=v^{2x}-v^{2x-1}$。

把这两种情况加起来就能得到正确的递推式子：$f(x)=v^{2x}-v^{2x-1}+v\times f(x-1)$。

当然边界情况是 $f(1)=v^2-v+1$，即二元限制的第一个数与左边的数不同的 $v(v-1)$ 种情况，加上这两个数相同则右边的两个数也必须相同的 $1$ 种情况。

好的，先别急着直接开始写代码递推，看看继续推式子能不能推出点什么。

$$f(x)=v^{2x}-v^{2x-1}+v\times(v^{2x-2}-v^{2x-3}+v\times f(x-2)) $$$$f(x)=v^{2x}-v^{2x-1}+v^{2x-1}-v^{2x-2}+v^2\times f(x-2) $$$$f(x)=v^{2x}-v^{2x-2}+v^2\times f(x-2)$$

嗯？好像有点东西，继续推推看？

$$f(x)=v^{2x}-v^{2x-2}+v^2\times(v^{2x-4}-v^{2x-5}+v\times f(x-3)) $$$$f(x)=v^{2x}-v^{2x-2}+v^{2x-2}-v^{2x-3}+v^3\times f(x-3) $$$$f(x)=v^{2x}-v^{2x-3}+v^3\times f(x-3)$$

没错，经过推理我们得到了 $f(x)=v^{2x}-v^{2x-k}+v^k\times f(x-k)$。接着带入 $k=x-1$：

$$\begin{aligned}f(x)&=v^{2x}-v^{x+1}+v^{x-1}\times (v^2-v+1)\\&=v^{2x}-v^{x+1}+v^{x+1}-v^x+v^{x-1}\\&=v^{2x}-v^x+v^{x-1}\end{aligned} $$

套上个快速幂，$f(x)$ 就能 $O(\log x)$ 求出了。

最终答案是每两个限制之间的区间的情况数相乘，还要再乘上开头和末尾连续段的答案：

• 对于开头，因为没有左端点的限制，只要避免踩中任何一个二元限制就可以填出。所以这一段的二元限制是什么都没关系。答案为 $v^{2x}$。
• 对于末尾，因为没有右端点的限制，所以如果有二元限制就按着二元限制填，没有就随便填，也一定可以把这里的数填出。所以这一段的二元限制是什么也没关系。答案为 $v^{2x}$。

把所有区间的答案乘起来再输出即可，记得取模。算上刚开始需要的排序，时间复杂度为 $O(Tm(\log n+\log m))$，其中的 $\log n$ 是快速幂带来的。

这里会有一些对题解内容的补充以及赛时代码。