一篇小总结，已放入 Re：从零开始的生成函数魔法。
主要介绍利用多项式思想与生成函数解决序列上的求和问题。
1. 集合积和
- 给出 \(n\) 个变量 \(a_1,a_2,\cdots,a_n\) 的取值，对所有 \(k \in [0,m]\) 求所有它们能组成的 \(k\) 次单项式的和。
- \(n,m \leq 10^5\)。
注：为了方便计算时间复杂度，下文中假设 \(n,m\) 同阶。
似乎无法因式分解，考虑用生成函数，直接考虑每个变量的次数：
\[Ans_k=[x^k]\prod\limits_{i=1}^n(1+a_ix+a_i^2x^2+\cdots)=[x^k]\prod\limits_{i=1}^n \dfrac{1}{1-a_ix} \]使用分治 + NTT，可在 \(O(n \log^2n)\) 内算出。
发现答案是一堆多项式之积的形式，这是一个很好的形式。
事实上 Matrix-Tree 定理也是这个形式，因此下面许多变式的技巧都可以套到 Matrix-Tree 定理上
2. 无序背包
随便思考一下，其实就是 \(n\) 种体积为 \(1\) 的物品，第 \(i\) 种物品有 \(a_i\) 种方案（同种物品不同件的方案是区分的），正好填满大小为 \(k\) 的背包的方案数。
拓展 1：每种物品有体积
设第 \(i\) 种物品的体积为 \(V_i\)，则：
\[Ans_k=[x^k]\prod\limits_{i=1}^n \dfrac{1}{1-a_ix^{V_i}} \]其实就是 P4389 付公主的背包。
实现方式：取 ln 后用 \(\ln(1-x)\) 的泰勒展开，再分治 + FFT，\(O(n \log^2n)\)。
拓展 2：每种物品数量有限制
设第 \(i\) 种物品的体积为 \(t_i\) 件，则：
\[Ans_k=[x^k]\prod\limits_{i=1}^n(1+a_ix+a_i^2x^2+\cdots+a_i^{t_i}x^{t_i})=[x^k]\prod\limits_{i=1}^n \dfrac{1-a_i^{t_i+1}x^{t_i+1}}{1-a_ix} \]实现方式：分子分母可以分别处理，分子还是取 \(\ln\)，\(O(n \log^2n)\)。
其实好像是没啥用的……但是有个特例：
3. 01 背包
当 \(t_i=1\) 时，\(Ans_k=[x^k]\prod\limits_{i=1}^n (1+a_ix)\)。
它代表的意义就是单项式的每个变量的次数不超过 \(1。\)
什么意思？就是 \(a_i\) 中任选 \(k\) 个（不能重复）乘起来再求和。形式化的：
\[Ans_k=\sum\limits_{S \subseteq \{1,2,\cdots,n\}} [|S|=k] \prod\limits_{i \in S} a_i \]这个巧妙的意义使它很容易在题目中出现：
-
CF109C Lucky Tree ：将条件改为 \(n\) 元组，且任意两点间有关键边，可转化为这个模型。
-
P3909 异或之积：其实是积之和，而且 \(k=3\) （
这还需要生成函数？）。 -
P5326 [ZJOI2019]开关：最后一步的处理就是这个模型（变式）。
-
Open Cup XXI / Gym102978F Find the LCA：也要用到这个模型（变式）。
另外，拓展的韦达定理也可以这样来理解。
接下来我们把重心放在这个模型的变式上：更多限制，或者说更多维度。
变式 1：Min / Max
以 Open Cup XXI / Gym102978F Find the LCA 为例，推到最后要求：
-
\[Ans_k=\sum\limits_{S \subseteq \{1,2,\cdots,n\}} [\min S=k] \prod\limits_{i \in S} a_i
\]
注意这里没有限制 \(S\) 的大小。
想法也很简单，直接暴力枚举最小值：
\[Ans_k=[x^k]\sum\limits_{i=1}^n a_ix \prod\limits_{j=i+1}^n (1+a_jx) \]看上去很不可做，但实际上也可以分治 + FFT，\(O(n \log^2 n)\)。
变式 2：高维权值
以 P5326 [ZJOI2019]开关 为例（
尽管这道题并不需要也不是重点）。 -
给定集合 \(S\)，求：
-
\[Ans_k=\sum\limits_{T \neq \empty} [2 \nmid |S \bigcap T|][\sum\limits_{i \in T} w_i=k] 1
\]
这里实际上有点不太一样，是 有体积的背包 并且 \(a_i=1\)，不过大同小异。
可以发现这里有两个条件，上面的模型看似无法扩展。
我们可以尝试给每个变量的权值再加上一维，来满足额外的条件。
这里要数 \(S\) 与 \(T\) 都有的个数，就设权值 \(b_i=[i \in S]。\)
\[Ans_k=\sum\limits_{2 \nmid t} [x^ky^t]\prod\limits_{i=1}^n (1+x^{w_i}y^{b_i}) \]高维多项式不好处理，但发现只需要计算 \(y\) 的次数为奇数的系数，可以用单位根反演。
令 \(y=-1\) 与 \(y=1\)，得到：
\[Ans_k=[x^k]\dfrac{\prod\limits_{i=1}^n (1+x^{w_i}) - \prod\limits_{i=1}^n (1+x^{w_i}(-1)^{b_i}) }{2} \]\(O(n \log^2 n)\)。
异或之和
-
给出 \(n\) 个数 \(a_1,a_2,\cdots,a_n\) ，对所有 \(k \in [0,m]\) 求所有任选 \(k\) 个数的异或之和。
-
\(n,m \leq 10^5\)。
首先显然每一位是相互独立的，所以可以拆位，现在问题变成了权值只有 \(0\) 和 \(1\)。
现在问题变成了权值只有 \(0\) 和 \(1\)
那若干个数的异或和为 \(1\) 当且仅当有奇数个数的权值为 \(1\)，只要算出方案数就好了
和刚才的 高维权值 差不多，设权值 \(b_i=w_i\)。
\[Ans_k=\sum\limits_{2 \nmid t} [x^ky^t]\prod\limits_{i=1}^n (1+x^{w_i}y^{b_i}) \] \[Ans_k=[x^k]\dfrac{\prod\limits_{i=1}^n (1+x^{w_i}) - \prod\limits_{i=1}^n (1+x^{w_i}(-1)^{b_i}) }{2} \]完全一样的，不再解释了。
另：可以拓展至 \(w\) 进制的异或和，对每一种答案做一遍即可，\(O(wn \log^2 n)\)。
4. 有序背包
我们的背包刚才是一种一种选的，不考虑顺序.
如果考虑顺序，相当于每种方案乘上了一个可重排列。
好像正好和指数型生成函数的乘法对应上了！
\[(a_1+a_2+\cdots+a_n)^k=k![x^k]\prod\limits_{i=1}^n e^{a_ix}=k![x^k] e^{\sum_{i=1}^n a_i x} \]同时这也对应着多项式定理。
又是乘法的形式，只不过是 EGF 的。
可以用在 Matrix-Tree 定理上：P5296 [北京省选集训2019]生成树计数。
更好玩的来了：我们完全可以把它套在 01 背包 的模型上！
\[Ans_{k,p}=\sum\limits_{S \subseteq \{1,2,\cdots,n\}} [|S|=k] (\sum\limits_{i \in S} a_i)^p \]直接套，得到：
\[Ans_{k,p}=p![x^ky^p]\prod\limits_{i=1}^n (1+e^{a_iy}x) \]不考虑 \(k\) 的话，即令 \(x=1\)，可以通过一系列技巧做到 \(O(\sum a_i \log^2 \sum a_i)\)。
5.. 和之积
\[\prod\limits_{i=1}^n (a+b_i)=[x^n] \dfrac{1}{1-ax} \prod\limits_{i=1}^n (1+b_ix) \]类似二项式定理拓展的东西。
其实就是从 \(n\) 个括号里选若干个 \(b_i\)，剩下的用 \(a\) 补齐。
考虑用多项式的乘积来表示，将 \(a\) 单独用一个多项式 \(1+ax+a^2x^2+\cdots\) 表示；\(b_i\) 由于不能重复，用 \(n\) 个多项式 \(1+b_ix\) 表示：
\[\prod\limits_{i=1}^n (a+b_i)=[x^n] (\sum\limits_{i=0}a^ix^i) \prod\limits_{i=1}^n (1+b_ix)=[x^n] \dfrac{1}{1-ax} \prod\limits_{i=1}^n (1+b_ix) \]题目：GYM102978D Do Use FFT，非常巧妙地用这个式子化简，从中也可以看到将朴素问题转化为多项式表示的优势。