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

cff_0102 · 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-k}+v^k\times f(x-k)。接着带入 k=x-1：

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

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

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

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

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