NOI2019

机器人

多项式优化 DP？首先有简单的 $O(n^2V)$ 区间 DP，发现每个区间的 $f$ 是关于 $v$ 的 $O(r-l)$ 次多项式，于是直接维护。前缀和可以拉格朗日插值预处理。

❄ ​斗主地

Nep？！

结论是一次函数进行一次操作后还是一次函数，二次函数进行一次操作后还是二次函数，然后随便找三个值就行了。

证明按函数解析式算一遍一次操作后的就行。倒数第 $i$ 位为上面（下面）的倒数第 $a$ 位的概率如下

$$\frac{\binom{i-1}{a-1}\binom{X+Y-i}{X(Y)-a}}{\binom{X+Y}{X}}$$

💩 ​I 君的探险