洛谷5326 [ZJOI2019]开关
Luogu LOJ 分析 设 $P=\sum_{i=1}^n p_i$。 设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。 $F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有 直接计算即可。 代码 // ==================================== //...
Luogu LOJ 分析 设 $P=\sum_{i=1}^n p_i$。 设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。 $F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有 直接计算即可。 代码 // ==================================== //...
Luogu LOJ 分析 我们画出每条路线的 $t-E$ 图像，大概是这个样子的（蓝色的是原函数，红色的是它的导数）： 感性理解一下可以知道，最后每条路径在其消耗的能量处的导数相同。 于是我们可以二分这个导数，然后把每段的速度求出来，算一下总能量是否 $\leq E_U$ 来 check。 现在考虑已知导数怎么算速度。我们有 这个东西在 $[v',+\infty)$ 上是单增的，所以同样...
Luogu LOJ 分析 一种 FFT 做法 考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。 可以发现转移是一个多项式快速幂，于是直接 FFT 就可以了。 （大概）可以理解成概率生成函数卷积？ 然而 FFT 掉精度很严重，我只能过 $60$ 分。所以对于大数据要考虑其它做法。 一种定积分做法 首先要知道中心极限定理的一个推论： 设有 $n$ 个独立同分...