互测搬的题。教练整的 PDF LaTeX 全炸了，我在这里再发一遍。（虽然也不会有人看）
题目来源：CF755G
\(5pts\) 做法
我会爆搜！
直接 DFS 枚举选择方案。
\(20pts\) 做法
我会 DP！
设 \(f_{i.j}\) 表示考虑前 \(i\) 个球，已经选出了 \(j\) 组的方案数，那么不难得出转移式：
\[f_{i,j} = f_{i - 1, j} + f_{i - 1, j - 1} + f_{i - 2, j - 1} \]于是复杂度 \(O(nk)\)。
\(k=1\)
选组大小为 \(1\) 的方案数为 \(n\)，大小为 \(2\) 的方案数为 \(n-1\)，所以答案等于 \(2n - 1\)。
\(k=2\)
分三种情况考虑：
- 两组大小都为 \(1\)：\(\binom{n}{2}\)
- 一组为 \(1\)，另一组为 \(2\)：考虑先从 \(n - 1\) 的序列中选两个数，然后在第二个数后面加一个数，左右翻转也一样，那么答案就是 \(2\binom{n - 1}{2}\)。
- 两组都为 \(2\)：考虑从 \(n-2\) 的序列中选两个数，然后在左面的数的左侧、右面的数的右侧加一个数，那么答案就是 \(\binom{n-2}{2}\)。
\(O(n \log ^2 n)\) 做法
其实做到 DP 这一步你就应该想到一些什么吧）
假如我们把 \(f_{i,j}\) 看作一个关于 \(j\) 的生成函数 \(F_i\)，那么就可以把 DP 写成以下的形式：
\[F_i=F_{i-1}+xF_{i-1}+xF_{i-2} \]也就是：
\[F_i=(1+x)F_{i-1}+xF_{i-2} \]这东西其实就是一个生成函数的递推式，于是我们有一个非常弱智的做法：直接矩阵快速幂。这样复杂度就是 \(O(n \log^2 n)\) 的，足以通过此题。
还有一个做法是倍增 FFT，对一开始的 DP 式子进行一些更改可以推出 \(G_{2n},G_{2n+1},G_n\) 的关系，不过我太菜了确实看不出怎么更改成这样的形式，所以想看的自己看题解吧。
\(O(n \log n)\) 做法
其实写出来上面的做法就够了，这个做法比较无脑：
考虑我们得到了 \(F_i=(1+x)F_{i-1}+xF_{i-2}\) 这样的一个递推式，我们直接解这个递推式。
它的特征方程为 \(\lambda^2=(1+x)\lambda+x\)，解得 \(\lambda_1=\frac{1+x+ \sqrt{x^2+6x+1}}{2}, \lambda_2=\frac{1+x- \sqrt{x^2+6x+1}}{2}\)。
那么 \(F_n = A \times \lambda_1^n + B \times \lambda_2^n\)。
\[\begin{cases} F_0=A+B=1\\ F_1=A \lambda_1 + B \lambda_2=1+x \end{cases} \]解得：
\[\begin{cases} A=\frac{\lambda_1}{\sqrt{x^2+6x+1}}\\ B=\frac{-\lambda_2}{\sqrt{x^2+6x+1}}\\ \end{cases} \]于是：
\[F_n=\frac{\lambda_1^{n+1}-\lambda_2^{n+1}}{\sqrt{x^2+6x+1}} \]由于 \(\lambda_2\) 是不存在常数项的（\(\sqrt{x^2+6x+1}\) 的常数项肯定是 \(1\)），所以 \(\lambda_2^{n+1}\) 的最低次项也是 \(n+1\) 次的，而大于 \(n\) 答案肯定是 \(0\)，所以这一项我们就直接不计算了，也就是我们直接计算：
\[\frac{1}{\sqrt{x^2+6x+1}} \left(\frac{1+x+ \sqrt{x^2+6x+1}}{2}\right)^n \pmod{x^{n+1}} \]然后就可以直接上多项式全家桶就可以做到 \(O(n \log n)\) 了。
标签：Balls,frac,log,Many,CF755G,sqrt,6x,做法,lambda From： https://www.cnblogs.com/apjifengc/p/17021697.html