浅谈积和类问题

更好的阅读体验

一篇小总结，已放入 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 背包 的模型上！

U164351 繁星

\[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) \]