题解：P11362 [NOIP2024] 遗失的赋值

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

没有其它要求，一个二元限制的可能数为 $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$：

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

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

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

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