题解 CF755G 【PolandBall and Many Other Balls】

· · 题解

依照题意我们可以直接列出生成函数

[x^n]\frac{1}{1-(x+xt+x^2t)}

对此进行各种代数变形就可以得到不同的做法. 这里给出最低复杂度的做法，考虑将上式看做关于 x 的线性递推，即得

\frac{r_1^{n+1}-r_2^{n+1}}{r_1-r_2}

其中 r_1,r_2 是代数方程 r^2-(1+t)r-t=0 的两个根. 如果展开来写就是

\frac{(1+t+\sqrt{1+6t+t^2})^{n+1}-(1+t-\sqrt{1+6t+t^2})^{n+1}}{2^{n+1}\sqrt{1+6t+t^2}}

由于 (1+t-\sqrt{1+6t+t^2}) 的常数项为 0 ，所以做 n+1 次幂后从 n+1 次项才开始有值，所以我们只需要考虑计算

\frac{(1+t+\sqrt{1+6t+t^2})^{n+1}}{2^{n+1}\sqrt{1+6t+t^2}}

我们知道这是一个整式递推. 具体地，设 k=n+1，那么整式递推式为

\begin{aligned} n(k-n)f_n=&\left[(k-1)(2k-3)-5(k-3)(n-1)+5(n-1)(n-2)\right]f_{n-1}\\ &\ +\left[-2(k+1)(k-1)+5(k-1)(n-2)f_{n-2}-5(n-2)(n-3)\right]f_{n-2}\\ &\ +\left[(k-1)+(k-3)(n-3)-(n-3)(n-4)\right]f_{n-3} \end{aligned}

初值为

\begin{aligned} f_0&=1\\ f_1&=2k-3\\ f_2&=2k^2-10k+13\\ f_3&=\frac{4}{3}k^3-14k^2+\frac{152}{3}k-63 \end{aligned}

推导我也不会，我拿电脑算的（雾）

于是本题可以在 O(n) 甚至 O(\sqrt{n}\log n) 时间内完成.