洛谷3779 [SDOI2017]龙与地下城
Luogu LOJ 分析 一种 FFT 做法 考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。 可以发现转移是一个多项式快速幂，于是直接 FFT 就可以了。 （大概）可以理解成概率生成函数卷积？ 然而 FFT 掉精度很严重，我只能过 $60$ 分。所以对于大数据要考虑其它做法。 一种定积分做法 首先要知道中心极限定理的一个推论： 设有 $n$ 个独立同分...
Luogu LOJ 分析 一种 FFT 做法 考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。 可以发现转移是一个多项式快速幂，于是直接 FFT 就可以了。 （大概）可以理解成概率生成函数卷积？ 然而 FFT 掉精度很严重，我只能过 $60$ 分。所以对于大数据要考虑其它做法。 一种定积分做法 首先要知道中心极限定理的一个推论： 设有 $n$ 个独立同分...