[FJ2021]D2T3题解

考试的时候一点思路没有，最近听福州的神仙的一些做法。

想自己推一下。

题目大概是这样的

\(a_i = \frac{i\ *\ a_{i - 1} \ + \ i\ * \ (i\ -\ 1)\ * \ a_{i - 2}}{2}+(-1)^i * (1 - \frac{i}{2})\)

\(s_i = \sum_{i = 1}^n C^{n}_{n - i} * (n - i + 1) a_i\)

设母函数\(S(x) = \sum_{i = 0}^{\infty} s_i x^i\)

\(G(x) = \sum_{i = 0}^{\infty} \frac{a_i}{i!} x^i\)

\(F(x) = \sum_{i = 0}^{\infty} \frac{i + 1}{i!} x^i\)

考虑生成函数卷积。

\(S(x) = n!G(x)*F(x)\)

\(F(x) = \sum_{i = 0}^{\infty} \frac{i + 1}{i!} x^i\\=\sum_{i = 1}^{\infty}\frac{1}{(i - 1)!} x^i + \sum_{i = 0}^{\infty}\frac{1}{i!} x^i\\=xe^x + e^x\\=(1 + x)e^x\)

考虑\(G_i = \frac{a_i}{i!}\)

\(2G_i =G_{i - 1} + G_{i - 2} + \frac{(-1)^{i - 1}\ (i - 2)}{i!} - 2[i = 0] + [i = 1] + [i = 2]\\ =G_{i - 1} + G_{i - 2} + \frac{(-1)^{i - 1}}{(i - 1)!} + \frac{(-1)^{i}\ 2}{i!} - 2[i = 0] + [i = 1] + [i = 2]\)

所以\(2G(x) = xG(x) + x^2G(x) + \sum_{i = 1}^{\infty}\frac{(-1)^{i - 1}}{(i - 1)!}x^i + 2\sum_{i = 0}^{\infty}\frac{(-1)^{i}}{(i)!}x^i - 2 + x + x ^ 2\\=
xG(x)+x^2G(x) + xe^{-x} + 2e^{-x} - 2 + x + x ^ 2\)

所以有\((2 - x - x^2)G(x) = （2 + x）e^{-x} - （2 - x - x^2）\)

所以\(G(x) = \frac{e^{-x}}{1 - x} - 1\)

\(S(x) = n!(F(x)G(x))\\=n!((1 + x)e^x\frac{e^{-x}}{1 - x} - (1+x)e^x)\\=n!(\frac{1+x}{1-x} - (1+x)e^x)\\=n!((-1 + \frac{2}{1 - x})-(1+x)e^x)\\=n!\sum_{i = 0}^{\infty}2x^i - n! - n!\sum_{i = 0}^{\infty}\frac{i + 1}{i!}x^i\)

\(S_n = [x ^ n]S(x) = 2n! - n![x == 0] - n - 1\)

完了。

生成函数真好玩，感觉很奇妙的样子

巴特西

[FJ2021]D2T3题解

最新文章

热门文章