本博客在看完《多项式：从入门到全家桶》后食用更佳。
生成函数简介
省流：
普通生成函数： \(f(x)=\sum_i a_ix^i\)
指数生成函数： \(f(x)=\sum_i \frac{a_ix^i}{i!}\)
狄利克雷函数生成函数： \(f(x)=\sum_i\frac{a^i}{i^x}\)
普通生成函数（重点）
本章中记序列 \(a\) 的普通生成函数为 \(A(x)\) ，序列 \(b\) 的普通生成函数为 \(B(x)\) ，以此类推。
为下文叙述方便，再记 \(\langle a_t\rangle\) 为序列 \(a\) 的普通生成函数，即 \(A(x)=\langle a_t\rangle(x)\) 。
基本运算
加减法很显然。
\[\begin{aligned} \langle a_t\rangle+\langle b_t\rangle&=\langle a_t+b_t\rangle\\ \langle a_t\rangle-\langle b_t\rangle&=\langle a_t-b_t\rangle \end{aligned} \]乘法仔细想一想其实也不难，由基础的乘法分配律可知：
\[\langle a_t\rangle*\langle b_t\rangle=\left\langle \sum_{i=0}^t a_tb_{n-t}\right\rangle \]原本需要 \(O(n^2)\) 的时间计算，使用[FFT]或[NTT]即可加速到 \(O(n\log n)\)。
标签：langle,出门,入门,sum,生成,普通,rangle,函数 From： https://www.cnblogs.com/SqrtSecond/p/generating-function.html