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)=F(x)G(x)=\sum\limits_{i=0}^{n+m}(\sum\limits_{j=0}^ia_jb_{i-j})x^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，把两个乘起来就是

G(x)F(x)=\sum\limits_{i\geq0}(\sum\limits_{j=0}^ifib_js_{i-j})x^i\\ \because s_{i+1}=\sum\limits_{j=0}^ifib_js_{i-j}\\ \therefore G(x)F(x)=s_0+\sum\limits_{i>0}s_ix^i\\ =1+\sum\limits_{i>0}s_ix^i\\ =1+G(x)

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

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

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