XYD 7.26 记录

上午讲多项式和生成函数，之前只写过 FFT 和 NTT 的板子，其他都没做过，上午听懂了挺多的，不过到后面就掉线了，然后我就自己网上学了一下。感觉生成函数终于理解了，以前自己学的时候看到一个数列的生成函数 $\sum\limits_{i=0}^na_ix^i$ 就一直不明白 $x^i$ 到底干嘛的，为啥非要写成一个多项式的形式，今天终于是知道了。就是他是有一些组合意义的，比如说你要两组数加起来刚好是一个数 $s$ ，那你把他的方案数列出来就是 $\sum\limits_{i=0}^sf_if_{s-i}$ 这里 $f_i$ 就是取 $i$ 个有多少种取法，然后你考虑对于两个多项式 $F(x)=\sum\limits_{i=0}^na_ix^i,G(x)=\sum\limits_{i=0}^mb_ix^i$，如果把他们两个乘起来会发生什么。

然后你会惊奇的发现 $H(x)$ 的第 $s$ 项的系数就是 $\sum\limits_{i=0}^sa_ib_{s-i}$，刚好就是和上面的方案数的式子是同构的，非常巧妙，所以要把这两个结合起来，来表达同样的意思。

至于这个多项式就是纯推式子。

昨天紧急补习了 FFT，把第一题 分治 FFT 过了，中午听完课回来有些了几题生成函数的题目，就是因为只要推式子，推完了就是比较简单的快速幂什么的随便写一下就可以了，感觉就是小学奥数题，给你一个无穷大的数列让你求和，然后你要乘个什么东西上下消掉，然后就能推出来了，就和生成函数求他的封闭形式差不多。

拿 P4451 讲一下基本思路。斐波那契数列生成函数 $F(x)=\frac{x}{1-x-x^2}$，然后设总和恰好为 n 的答案记为 $s_n$，那么 $s_n=\sum\limits_{i=0}^{n-1}s_i\times fib_{n-i}$，他的生成函数 $G(x)=\sum\limits_{i=0}^{\infin}s_ix^i$，把两个乘起来就是

反正非常的聪明，然后两个多项式关系就有了并且 $F(x)$ 已知，所以直接求 $G(x)$ 取他 $x^n$ 的系数就可以了。

多项式就不说了，就是推式子，可能要代码技巧的我还没做。

今天我终于理解卷积是啥以及学会了初级的生成函数。