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

zgy_123 · 2024-11-30 16:05:40 · 题解

建议黄。赛时手搓了 129600 就会了，然而推错式子，45pts 遗憾离场。

按照考场思路写一下题解，个人认为是挺好理解的。下文将二元限制写作条件语句，一元限制写作赋值语句。

首先看到这个小样例解释，发现合法方案占大多数，可以用整体方案减去不合法。

显然任意选的方案数是 v^{2(n-1)}，而不合法有两种情况：

• 两个赋值语句矛盾。
• 根据一个赋值语句和假定的条件语句，推导出不等于另外几个赋值语句的值（如小样例第二组数据）。

然后看到第一个大样例，发现数比较小，可以手搓。前三组数据都没什么意思，直到第四组。它是这么个情况：

? 2 2 2 ? ? 2 ? ? 2

根据上文提到的猜想，要计算不合法方案的数量。由于每个条件语句一定是向后赋值，故从前向后考虑。分以下几步：

0. 总方案数为 v^{2(n-1)}=2^{18}=262144。
1. 由于 x_2 前面没有任何的赋值语句，所以不可能不合法。
2. 在 x_3 处不合法当且仅当 a_2=2 且 b_2\neq2，这个概率是 \frac{1}{4}。

• 为什么要计算概率而不是方案数？在下一步计算时有些情况已经被删掉，如果用方案数计算，仍要记录当前合法方案数，本质与计算概率再连乘相同。

3. 在 x_4 处不合法同上，概率为 \frac14。
4. 在 x_7 处不合法。这个是思路的关键。它前面最后一个赋值语句是 x_4=2，易证不合法只能是通过这个条件推出 x_5,x_6,x_7 而 x_7\neq2。那么它需要满足的条件即为：

这就是在 x_7 处不合法的充分必要条件。它发生的概率为 \frac12\times\frac12\times\frac12\times\frac12=\frac1{16}。

5. 在 x_{10} 处不合法，同上，概率为 \frac1{16}。

所以整个样例的合法情况数就是 262144\times(1-\frac14)\times(1-\frac14)\times(1-\frac1{16})\times(1-\frac1{16})=129600。

那么这个题就迎刃而解了。根据上文，可推出在当前赋值语句的 c 为 i，以前最后一个赋值语句的 c 为 j 的情况下，方案不合法的概率为 \frac1v\times\frac1v\times\frac1v\times\cdots\times\frac1v\times\frac{v-1}v=\frac{v-1}{v^{i-j+1}}，合法的概率为 \frac{v^{i-j+1}-(v-1)}{v^{i-j+1}}，累乘即可，除第一个赋值语句不计外不要考虑任何边界条件。

（本人考场推式子时将最后一项错写成 \frac1v，导致最后算出合法概率为 \frac{v^{i-j+1}-1}{v^{i-j+1}}，然而又恰好 v=2 时候时相等的，所以一直查不出来）。

代码没发下来不贴了。理解了以后有手都会写。