生成函数
我们可以把生成函数看作是代数对象，其形式上的处理使得人们可以通过代数手段计算一个计数问题。
通常 我们默认级数是收敛的。(主要原因在于代数手段往往是需要保证收敛的)
本文章不涉及多项式题目（交给考拉）
普通生成函数的定义为：
\[\displaystyle\sum_{n}a_nx^n \]常见的普通生成函数：
\[\begin{aligned} \displaystyle\sum_{i\ge 0}c^i x^{ik} &\xrightarrow{\text{OGF}} \dfrac{1}{1-cx^k} \\ \displaystyle\sum_{i\ge 0}\binom{n}{i}x^i &\xrightarrow{\text{OGF}} (1+x)^n \\ \displaystyle\sum_{i\ge 0}\binom{i+k-1}{k-1} &\xrightarrow{\text{OGF}} \dfrac{1}{(1-x)^k} \\ \displaystyle\sum_{i\ge 0}x^{2i} &\xrightarrow{\text{OGF}} \dfrac{1}{1-x^2} \\ \displaystyle\sum_{i\ge 0}\dfrac{c^i x^i}{i!} &\xrightarrow{\text{OGF}} e^{cx} \\ \displaystyle\sum_{i>0}\dfrac{x^i}{i} &\xrightarrow{\text{OGF}} \text{ln}(1-x) \\ \displaystyle\sum_{i>0}\dfrac{(-1)^{n-1}x^n}{n} &\xrightarrow{\text{OGF}}\text{ln}(1+x) \end{aligned} \]基本运算：
\[\begin{aligned} (\displaystyle\sum_{n}f_nx^n)\pm(\displaystyle\sum_{n}g_nx^n)&=\displaystyle{\displaystyle\sum_{n}(f_n \pm g_n)x^n} \\ c\times (\displaystyle\sum_{n}f_nx^n)&=\displaystyle\sum_{n}c\times f_nx^n \\ (\displaystyle\sum_{n}f_nx^n)(\displaystyle\sum_{n}{g_nx^n})&=\displaystyle\sum_{n}(\displaystyle\sum_{i=0}^{n}f_ig_{n-i})x^n \end{aligned} \]小应用：求一个排列关于逆序对个数的生成函数：
\[\displaystyle\prod_{i=1}^{n}(\sum_{j=0}^{j-1}x_j)=\displaystyle\prod_{i=1}^{n}\dfrac{1-x^i}{1-x} \]大概的意思就是刻画每个位置作为逆序对的后者出现了多少次。刚好每种不同的数量都对应着一个排列。
简单小练习：P2000 拯救世界（式子大多上面都写了，可以参考）
终于有例题了！
首先可以很好的列出生成函数：
\[\displaystyle\sum_{i=1}^{n}\sum_{j=0}^{m_i}x_j=\sum_{i=1}^{n}\dfrac{1-x^{m_i+1}}{1-x}=(1-x)^{-n}\sum_{i=1}^{n}1-x^{m_i+1} \]考虑 \((1-x)^{-n}\) 拆开得到：
\[(\prod_{i=1}^{n}1-x^{m_i+1})\sum_{j\ge 0}\binom{n+j-1}{j}x^j \]\(n\) 非常小，那么先用 \(2^n\) 枚举前面括号内的所有可能，最终得到一个多项式 \(p\)，至多有 \(2^ n\) 项。
差分，设 \(f(v)\) 表示糖果数小于等于 \(v\) 的所有方案的和，答案为 \(f(b)-f(a-1)\)。
考虑对于 \(p\) 的某一项 \(k\)，对 \(f(v)\) 的贡献即为：
\[p_k\sum_{i=0}^{v-k}\binom{n-1+i}{n-1}=p_k\binom{n+v-k}{n} \]相当于统计最后指数相加不超过 \(m\)，后一步是上指标求和。
注意到这题模数不友好，考虑把组合数写成下降幂形式，具体而言：
\[\binom{n}{m}=\dfrac{n^{\underline m}}{m!} \]还是不方便，注意到组合数的下指标很小很小，考虑可以求出下降幂对模数乘以 \(m!\) 取模，再除去 \(m!\) 后在对模数取模。
当然你也可以使用扩展卢卡斯，砍瓜切菜。
指数生成函数的定义为：
\[\sum_{i\ge 0}\frac{a_ix^i}{i!} \]常见的指数生成函数：
\[\begin{aligned} \sum_{i\ge0}\dfrac{c^ix^i}{i!}&\xrightarrow{\text{EGF}}e^{cx} \\ \sum_{i\ge0}\dfrac{x^{2i}}{(2i)!}&\xrightarrow{\text{EGF}}\dfrac{e^x+e^{-x}}{2} \\ \sum_{i\ge0}\dfrac{x^{2i+1}}{(2i)!}&\xrightarrow{\text{EGF}}\dfrac{e^x-e^{-x}}{2} \end{aligned} \]证明？泰勒展开（待学习）。
例题：用红白蓝三色给 \(1\times n\) 棋盘染色，要求红格颜色的个数是偶数，且至少有一个蓝色的方案数。
\[\begin{aligned} g(x)&=\sum_{i\ge 0}\dfrac{x^{2i}}{(2i)!}\sum_{i\ge 0}\dfrac{x^i}{i!}\sum_{i\ge 1}\dfrac{x^i}{i!} \\ &=\dfrac{e^x+e^{-x}}{2}e^x(e^x-1) \\ &=\dfrac{e^{3x}-e^{2x}+e^x-1}{2} \\ &=\dfrac{-1}{2}+\sum_{i\ge 0}\dfrac{3^n-2^n+1}{2}\dfrac{x^n}{n!} \end{aligned} \]那么可以得到：(式子外有常数项，要小心！)
\[h_n=\begin{cases} 0 & n=0 \\ \dfrac{3^n-2^n+1}{2} & n>0 \end{cases} \]这题跟 P2000 的本质区别在于这题方案是有序（相同的东西不做区分），因此考虑 \(\text{EGF}\)。
找到三种类型的基因分别对应的 \(\text{EGF}\)。
\[\begin{aligned} f(x)&=e^x\\ g(x)&=\dfrac{e^x+e^{-x}}{2}\\ h(x)&=\dfrac{e^x-e^{-x}}{2} \end{aligned} \]那么答案为
\[\begin{aligned} ans&=[x^n](f(x)g(x)h(x))^4\\ &=[x^n](\dfrac{1}{4}e^x(e^{2x}-e^{-2x}))^4\\ &=[x^n](\dfrac{1}{4}(e^{3x}-e^{-x}))^4\\ &=[x^n]\dfrac{1}{256}(e^{12x}-4e^{8x}+6e^{4x}-4+e^{-4x}) \end{aligned} \]那么又根据：
\[\sum_{i\ge0}\dfrac{c^ix^i}{i!}\xrightarrow{\text{EGF}}e^{cx} \]\[ans=\dfrac{n!}{256}(\dfrac{12^n}{n!}-\dfrac{4\times 8^n}{n!}+\dfrac{6\times 4^n}{n!}+\dfrac{(-4)^n}{n!}) \]因为是 \(\text{EGF}\)，所以一定要记得乘以 \(n!\)
\[ans=\dfrac{1}{256}(12^n-4\times 8^n+6\times 4^n+(-4)^n) \]注意到这个模数又很不友好，考虑将 \(n\) 很小的时候暴力乘，大的时候约分一手。
\[ans=81\times 12^{n-4}-8^{n-2}+6\times 4^{n-4}+(-4)^{n-4} \]然后你写了个快速幂，高高兴兴的交上去，发现 TLE 了！
出题人很没素质地卡了常。
需要使用扩展欧拉定理将指数减到模数级别，还可以再配合光速幂可以更快。
看到这里你就成功入门生成函数了！
标签：函数,dfrac,sum,生成,ge,text,aligned,displaystyle From： https://www.cnblogs.com/Hanghang007/p/18158383