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

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

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

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

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

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

? 2 2 2 ? ? 2 ? ? 2

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

这就是在 $x_7$ 处不合法的充分必要条件。它发生的概率为 $\frac12\times\frac12\times\frac12\times\frac12=\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$ 时候时相等的，所以一直查不出来）。

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