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

· · 题解

前言

赛时 T1 唐太久（Only get 40pts），切 T2 的时候人都傻了，看来开赛先看一遍题目是有道理的。

别看这篇题解长，如果仔细读下来，你会发现这题其实还是挺简单的。

思路

当一元约束之间有冲突的时候，答案很明显是 0。

考虑一元约束什么时候会与二元约束产生冲突：当且仅当有一对 i,j，满足：

因为只有这样，才能使 x_i,x_{i+1},\dots,x_{j-1} 的值都固定，并在 x_j 上产生冲突。

考虑到此时我们是让 x_j 产生冲突，与 i 是多少没有关系，为了统计的不重不漏，不妨将所有一元约束按位置排序后，使 i=c_p,j=c_{p+1}(1\le p<m)。特别地，当 m=1 时，约束条件可以任取，由于 a_i,b_i\in [1,v]，则答案即为 v^{2\times (n-1)}。

接下来，计算约束条件在 x_i 到 x_j（即 a_i,b_i 到 a_{j-1},b_{j-1}）上的合法方案数，再将它们连乘，即为总的合法方案数（其实还要考虑 1 到 c_1 与 c_m 到 n 的冗余）。但直接计算合法方案数是困难的。正难则反，考虑计算所有方案数减去不合法的方案数。

由于 a_i,b_i\in [1,v]，所有方案数即为 v^{2\times(j-i)}。而对于不合法方案数，因为要满足上述条件，所以 a_i 只有一种选择，而对于 p\in[i,j-2]，b_p 有 v 种选择，a_{p+1} 有 1 种选择（能且只能等于 b_p）。最后，b_{j-1} 有 v-1 种选择（不能等于 x_j）。综上，不合法方案数为 v^{j-i-1}\times (v-1)，则合法方案数即为：

v^{2\times(j-i)}-v^{j-i-1}\times (v-1)

由于最后的答案要连乘，则最后的答案为（数组 c 为升序排列）：

\Pi_{i=2}^m (v^{2\times(c_i-c_{i-1})}-v^{c_{i}-c_{i-1}-1}\times (v-1))

吗？

正如前文所说，还要考虑 1 到 c_1 与 c_m 到 n 的冗余，即约束 a_1,b_1 到 a_{c_1-1},b_{c_1-1} 和 a_{c_m},b_{c_m} 到 a_{n-1},b_{n-1} 的冗余。因为这一部分的 a 数组和 b 数组取 [1,v] 的任意一个数都没有问题，所以答案还要乘上 v^{2\times (c_1-1+n-c_m)}。

则，最终答案为：

v^{2\times (c_1-1+n-c_m)}\times \Pi_{i=2}^m (v^{2\times(c_i-c_{i-1})}-v^{c_{i}-c_{i-1}-1}\times (v-1))

代码实现是简单的，将 c 排序后使用快速幂计算并取模即可，记得最后把负数转成正数。

后记

个人认为这题是一道比较好的数学计数题，虽然放 T2 确实有点搞心态。

其实完全可以把数组 d 去掉，然后加上点奇奇怪怪的题目描述让这道题看起来很难（

因为是在回来的动车上用手机写的题解，数学公式难免有疏漏之处，若有请指出。

祝大家 NOIP2024 后的下一个赛程 rp++。