LuoGu: CF755G PolandBall and Many Other Balls
CF: G. PolandBall and Many Other Balls
写出DP方程， $f _ {i, j}$ 表示当前有 $i$ 组，用了前 $j$ 个球的方案数，那么有 $f _ {i, j} = f _ {i, j - 1} + f _ {i - 1, j - 1} + f _ {i - 1, j - 2}$ ，注意到 $n$ 很大， $k$ 较小，对于每一个 $n$ ，考虑一个 $k$ 项 OGF ，写作生成函数的形式，有 $F _ n = (1 + x) F _ {n - 1} + x F _ {n - 2}$ 。有特征方程 $z ^ 2 - (1 + x) z - xz = 0$ 。解得 $z _ 1 = \frac {1 + x + \sqrt {x ^ 2 + 6x + 1}} 2, z _ 2 = \frac {1 + x - \sqrt {x ^ 2 + 6x + 1}} 2$ 。设 $F _ n = c _ 1 z _ 1 ^ n + c _ 2 z _ 2 ^ n$ ，代入 $F _ 0 = 1, F _ 1 = 1 + x$ 入上式，那么有 $c _ 1 = \frac {1 + x}{2\sqrt {x ^ 2 + 6x + 1}} - \frac 1 2, c _ 2 = -\frac {1 + x}{2\sqrt {x ^ 2 + 6x + 1}} + \frac 1 2$ ，那么有 $F _ n = \frac 1 {\sqrt {x ^ 2 + 6x + 1}} (\frac {1 + x + \sqrt {x ^ 2 + 6x + 1}} 2 ) ^ {n + 1}$ 。
查看代码
1 |