形式幂级数的更多运算
形式幂级数与幂级数的比较
- 形式幂级数本质是序列（\(x^i\) 无意义），幂级数本质是极限。
- 形式幂级数通过带入 \(x\) 还原成幂级数。
- 假设系数在 \(\mathbb{C}\) 上，可以证明形式幂级数与具有正收敛半径的幂级数在 '通常' 的所有运算上服从同样规律（加减乘除求导积分……）。
形式幂级数的更多运算
假设 \(f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^{n} + \cdots\)。
求导
定义 \(f(x)\) 的导数为 \(a_1 + 2a_2x + \cdots + (n + 1)a_{n + 1}x^{n} + \cdots\)，记做 \(f'(x)\) 或 \(\dfrac{df(x)}{d(x)}\)。
对于形式幂级数而言，
求导是序列上的一个变换，即 \(\{a_0, a_1, \cdots, a_n,\cdots\} \Rightarrow \{a_1, 2a_2, \cdots, (n + 1)a_{n + 1},\cdots\}\)
积分
定义 \(f(x)\) 的积分为 \(a_0x + \dfrac{a_1}{2}x^2 + \cdots + \dfrac{a_{n - 1}}{n}x^{n} + \cdots\)，记做 \(\int f(x)dx\) 或 \(\int_{0}^{x} f(y)dy\)。
即 \(\{a_0, a_1, \cdots, a_n,\cdots\} \Rightarrow \{0, a_0, \dfrac{a_1}{2}, \cdots, \dfrac{a_{n - 1}}{n},\cdots\}\)。
推论：如果 \([x^0]f(x) = 0\)，令 \(g(x) = f'(x)\)，则 \(\int g(x)dx = f(x)\)。
复合
假设 \(f(x) = a_1x + a_2x^2 + \cdots + a_nx^{n} + \cdots, \ g(x) = b_0 + b_1x + b_2x^2 + \cdots + b_nx^{n} + \cdots\)。
则 \(g\) 复合 \(f\) 定义为 \(c_0 + c_1x + \cdots c_nx^n + \cdots\)，满足 \(c_0 = b_0, \ c_n = \sum\limits_{k = 1}^{n}b_k\sum\limits_{i_1 + i_2 + \cdots+ i_k = n}\prod a_{i_j}\)。
记做 \(g \circ f\) 或 \(g(f(x))\)。
如果 \(f\) 的常数项不为 \(0\)。
那么 \(c_0 = b_0 + b_0a_0 + b_0a_0^2 + \cdots + b_na_0^n + \cdots\)。
则 \(c_0\) 本身就是一个极限的形式，涉及到收不收敛的问题，这是在形式幂级数中不愿看到的。
因此在定义复合时，一般令 \([x^0]f(x) = 0\)。
再考虑 \(c_n = \sum\limits_{k = 1}^{n}b_k\sum\limits_{i_1 + i_2 + \cdots+ i_k = n}\prod a_{i_j}\)。
如果 \(i_j > n\)，那么 \(\sum{i_j} > n\)，所以 \(c_n\) 的定义不需要考虑收敛。
- \(\exp(x) = \sum_{n \ge0} \dfrac{1}{n!}x^n\)。
- \(\ln (1 + x) = \sum_{n \ge 1}(-1)^{n + 1}\dfrac{x^n}{n}\)。
- \(\ln (1 - x) = -\sum_{n \ge 1}\dfrac{x^n}{n}\)。
- 设形式幂级数 \(f(x)\) 满足 \([x^0]f(x) = 0\)，则可定义 \(\exp(f(x))\) 和 \(\ln(1 + (f(x))\)。（或 \([x^0] = 1\) 可定义 \(\ln(f(x))\)）。
- \(g(x) = \exp(f(x)) \iff f(x) = \ln(g(x))\)。
推论：\((g \circ f)' = (g' \circ f) \cdot f'\)。
假设 \(f(x) = \sum_{i \ge 1} a_ix^i, \ g(x) = \sum_{i \ge0}b_i, \ g(f(x)) = \sum_{i \ge0}c_ix^i\)。
满足
\[\begin{cases} f'(x) = \sum_{n \ge 0} (n + 1)a_{n + 1}x^{n} & a_0 = 0\\ \\ g'(x) = \sum_{n \ge 0} (n + 1)b_{n + 1}x^{n}\\ \\ g(f(x))' = \sum_{n \ge 0} (n + 1)c_{n + 1}x^{n} & c_0 = b_0, \ c_n = \sum\limits_{k = 1}^{n}b_k\sum\limits_{i_1 + i_2 + \cdots+ i_k = n}\prod a_{i_j}\\ \\ g'(f(x)) = \sum_{n \ge 0} d_{n}x^{n} & d_n = \sum\limits_{k = 0}^{n}(k + 1) \cdot b_{k + 1}\sum\limits_{i_1 + i_2 + \cdots+ i_k = n}\prod a_{i_j}\\ \end{cases} \]即证 \((n + 1)c_{n + 1} = \sum\limits_{i = 0}^{n}(i + 1)a_{i + 1}{}d_{n - i}\)。
左边：
\[\begin{aligned} \sum\limits_{i = 0}^{n}(i + 1)a_{i + 1}{}d_{n - i} &= \sum\limits_{i = 0}^{n}(i + 1)a_{i + 1}{}\sum\limits_{k = 0}^{n - i}(k + 1) \cdot b_{k + 1}\sum\limits_{i_1 + i_2 + \cdots+ i_k = n - i}\prod a_{i_j}\\ \\ &= \sum\limits_{k = 0}^{n}(k + 1) \cdot b_{k + 1}\sum\limits_{i = 0}^{n}(i + 1)a_{i + 1}{}\sum\limits_{i_1 + i_2 + \cdots+ i_k = n - i}\prod a_{i_j}\\ \\ &= \sum\limits_{k = 1}^{n + 1}k \cdot b_{k}\sum\limits_{i = 1}^{n + 1}i\cdot a_{i}{}\sum\limits_{i_1 + i_2 + \cdots+ i_{k - 1} + i = n + 1}\prod_{j = 1}^{k - 1} a_{i_j}\\ \\ &= \sum\limits_{k = 1}^{n + 1}k \cdot b_{k}\sum\limits_{i_1 + i_2 + \cdots+ i_{k - 1} + i = n + 1}a_{i_1}a_{i_2}\cdots a_{i_{k - 1}}\cdot a_i\cdot i \\ \\ &= \sum\limits_{k = 1}^{n + 1}b_{k}[\sum\limits_{i_1 + i_2 + \cdots+ i_{k - 1} + i_k = n + 1}a_{i_1}\cdots a_{i_k}\cdot i_1 + \sum\limits_{i_1 + i_2 + \cdots+ i_{k - 1} + i_k = n + 1}a_{i_1}\cdots a_{i_k}\cdot i_2 + \sum\cdots ] &\text{把 k 项拆开，每次选出一个特殊的 } i_j\\ \\ &= \sum\limits_{k = 1}^{n + 1}b_{k}\sum\limits_{i_1 + i_2 + \cdots+ i_{k - 1} + i_k = n + 1}(i_1 + i_2 +_ \cdots i_k)\prod_{j = 1}^ka_{i_j}\\ \\ &= \sum\limits_{k = 1}^{n + 1} b_{k}\sum\limits_{i_1 + i_2 + \cdots+ i_{k - 1} + i_k = n + 1}(n + 1)\prod_{j = 1}^ka_{i_j}\\ \end{aligned} \]右边：
\[\begin{aligned} (n + 1)c_{n + 1} &= (n + 1)\sum\limits_{k =1}^{n + 1}b_k\sum\limits_{i_1 + i_2 + \cdots+ i_k = n + 1}\prod_{i = 1}^ka_{i_j}\\ \end{aligned} \]左边等于右边。
计算 \(\ln(f(x))\)
（满足 \([x^0]f(x) = 1\)）重要观察：
\[\ln(f(x))' = \dfrac{1}{f(x)}f'(x) \]\(O(n)\) 求导，\(O(n\log n)\) 求逆，\(O(n)\) 积分。
计算 \(\exp(f(x))\)
（满足 \([x^0]f(x) = 1\)）如果 \(g(x) = \exp(f(x))\)，那么 \(\ln(g(x)) =f(x)\)。
构造牛顿迭代 \(h(g(x)) = \ln(g(x)) - f(x)\)。
有递推式
\[g(x) = g_0(x) \cdot[1 - \ln(g_0(x)) + f(x)] \pmod{x^{2n}} \]例题
三轮
题意：\(n\) 种商品，每种商品体积为 \(v_i\)，都有 \(10^5\) 件，输出凑成 \(1\) 到 \(m\) 的体积的总方案数。
对质数 \(19260817\) 取模 。（\(n, m, v_i \le 5\times 10^4\)）
\(v_i\) 至少为 \(1\)，可认为每种商品都有无穷件。
考虑其生成函数 \(F_i(x) = 1 + x^{v_i} + x^{2v_i} + \cdots = \dfrac{1}{1 - x^{v_i}}\)。
所以 \(G(x) = \prod\limits_{i = 1}^{k} \dfrac{1}{1 - x^{v_i}}\) 。
由于 \(v_i\) 很大，无法分治 ntt 求解。
将积化为和，两边取对数。
\[\begin{aligned} \ln(G(x)) &= \sum\limits_{i = 1}^{k} \ln\dfrac{1}{1 - x^{v_i}}\\ \\ &= \sum\limits_{i = 1}^{k} -\ln\ (1 - x^{v_i})\\ \\ &= \sum\limits_{i = 1}^{k} \sum_{j \ge 1} \dfrac{x^{v_ij}}{j} \end{aligned} \]第二类斯特林数
第二类斯特林数（斯特林子集数）\(\begin{Bmatrix}n\\ k\end{Bmatrix}\)，也可记做 \(S_2(n,k)\)，表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个互不区分的非空子集的方案数。
递推式
我们插入一个新元素时，有两种方案：
- 将新元素放入一个现有的非空子集，有 \(k\begin{Bmatrix}n-1\\ k\end{Bmatrix}\) 种方案。
- 将新元素单独放入一个子集，有 \(\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}\) 种方案；
边界是 \(\begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0]\)。
通项公式
不妨先认为 \(k\) 个集合互不相同，转化成经典容斥问题，最后乘上 \(\dfrac{1}{k!}\)。
则
重要公式
记下降阶乘幂 \(x^{\underline{n}}=\dfrac{x!}{(x-n)!}=\prod_{k=0}^{n-1} (x-k)\)。
则可以利用下面的恒等式将普通幂转化为下降幂：
\[x^n =\sum\limits_{k = 0}^n \begin{Bmatrix}n\\ k\end{Bmatrix} \begin{pmatrix}x\\ k\end{pmatrix} k! =\sum\limits_{k = 0}^n \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}} \]考虑各式组合意义。
- \(x^n \rightarrow\) \(n\) 个不同的球放入 \(x\) 个不同的盒子。
- \(\begin{pmatrix}x\\ k\end{pmatrix} \rightarrow\) \(x\) 个盒子中选出 \(k\) 个。
- \(\begin{Bmatrix}n\\ k\end{Bmatrix} \rightarrow\) \(n\) 个不同的球放入 \(k\) 个相同的盒子且都不为空。
- \(k! \rightarrow\) 将选出的 \(k\) 个盒子排列。
正确性显然。
指数生成函数
\[\sum_{n \ge 0} \begin{Bmatrix}n\\k\end{Bmatrix}\dfrac{x^n}{n!} = \dfrac{1}{k!}(\exp(x) - 1)^k \]不妨将盒子染成 \(k\) 种不同颜色，每种颜色在长度为 \(n\) 的排列中必须出现一次。
对于第一种颜色，\(F_1(x) = x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots = \exp(x) - 1\)（没有零次项，因为必须出现）。
全部的合法方案为 \([x^n]\prod F_i\)。
最后将染色去除，得到 \(G(x) = \dfrac{1}{k!}(\exp(x) - 1)^k\)。
第二类斯特林数·行
\[\begin{aligned} \begin{Bmatrix}n\\k\end{Bmatrix} &= \dfrac{1}{k!}\sum_{i = 0}^k(-1)^i\begin{pmatrix}k\\i\end{pmatrix}(k - i)^n\\ \\ &= \sum_{i = 0}^k\dfrac{(-1)^i}{i!}\dfrac{(k - i)^n}{(k - i)!}\\ \end{aligned} \]令 \(F(x) = \sum_{i \ge 0} \dfrac{(-1)^i}{i!}x^i \,, \ G(x) = \sum_{i \ge 0} \dfrac{i^n}{i!}x^i\)。
于是 \(S_2(n) = F * G\)。
第二类斯特林数·列
利用公式
\[\sum_{n \ge 0} \begin{Bmatrix}n\\k\end{Bmatrix}\dfrac{x^n}{n!} = \dfrac{1}{k!}(\exp(x) - 1)^k \]其中
\[f(x)^k = \exp(\ln f(x)^k) = \exp(k\ln f(x)) \]如果 \([x^0]f(x) \neq 1\) 则不能直接求对。
考虑给每项除以一个公因式 \(a_ix^i\)，满足第 \(i\) 项是系数非 \(0\) 的最低项。
最后再乘上 \((a_ix^i)^k\)。
EGF 求得的系数为 \(\dfrac{a_n}{n!}\)。
整数拆分
\(n\) 的 \(k\) 无序拆分
\(n\) 个无标号球分配到 \(k\) 个无标号盒子的方案数，满足每个盒子不为空，记为 \(p(n, k)\)。
递推关系
\[p(n, k) = p(n - 1, k - 1) + p(n - k, k) \]假设第 \(i\) 个盒子（第 \(i\) 行）里有 \(a_i\) 个球，满足 \(a_1 \ge a_2\cdots\ge a_k \ge 1\)。
分两部分考虑。
- 第 \(k\) 个盒子有且仅有新加入的一个球，方案为 \(p(n - 1, k - 1)\)。
- 第 \(k\) 个盒子不止一个球，把黄色一列去掉，方案为 \(p(n - k, k)\)。
常生成函数
考虑上图中有多少有 \(i\) 个球的列。
\(i\) 个球时，只能有 \(1\) 列，一种方案。
\(2i\) 个球时，只能有 \(2\) 列，一种方案。
因此其常生成函数为 \(F_i(x) = 1 + x^{i} + x^{2i} + \cdots = \dfrac{1}{1 - x^i}\)。
记 \(G_k = \prod_{i = 1}^kF_i\)。
由于至少要有一列为 \(k\)，所以
\[P_k(x) = G_k(x) - G_{k - 1}(x) = x^k\prod\limits_{i = 1}^k\dfrac{1}{1 - x^i} \]- 快速求 \(P_k\) 的前 \(n\) 项：对后式先取 \(\ln\) 再 \(\exp\)，详见 形式幂级数的更多运算-例题-三轮。\[\sum\limits_{i = 1}^{k} \ln\dfrac{1}{1 - x^{i}} = \sum\limits_{i = 1}^{k} \sum_{j \ge 1} \dfrac{x^{ij}}{j} \]
\(n\) 的无序拆分
\(n\) 个无标号球分配到一些无标号盒子的方案数，满足每个盒子不为空，记为 \(p(n)\)。
可知 \(p(n) = \sum_{k = 1}^np(n, k)\)。
常生成函数
延续上板的思考方向，行的个数没有限制，所以只要一些长度为 \(i\) 的凑出 \(n\) 个球即可。
那么
\[\begin{aligned} P(x) &=\prod_{i \ge 1}\dfrac{1}{1 - x^i}\\ \\ &= \exp\sum_{i \ge1}\sum_{j \ge 1}\dfrac{x^{ij}}{j}\\ \\ &= \exp\sum_{n \ge1}\sum_{d \mid n}\dfrac{x^{n}}{d}\\ \end{aligned} \]递推关系
证明繁琐，当结论记。
\[p(n) = \sum_{k \ge 1}(-1)^{k - 1}[p(n - \dfrac{3k^2 - k}{2}) + \dfrac{3k^2 -+ k}{2})] \]产生贡献的项只有 \(O(\sqrt N)\) 个，复杂度 \(O(N\sqrt N)\)。
主要运用于模数不友好的情况。
分配问题总结
\(n\) 个球放入 \(k\) 个盒子，球方案数。
\[\large \begin{array}{|c|} \hline n\text{ 个球} & k\text{ 个盒子} & \text{盒子可以为空} & \text{每个盒子至少一个球}\\ \hline \text{有标号} & \text{有标号} & k^n & k!\begin{Bmatrix}n\\k\end{Bmatrix}\\ \hline \\ \text{有标号} & \text{无标号} & \sum\limits_{i = 1}^k\begin{Bmatrix}n\\k\end{Bmatrix} & \begin{Bmatrix}n\\k\end{Bmatrix}\\ \hline \\ \text{无标号} & \text{有标号} & \begin{pmatrix}n + k - 1\\k - 1\end{pmatrix} & \begin{pmatrix}n - 1\\k - 1\end{pmatrix}\\ \hline \\ \text{无标号} & \text{无标号} & p(n + k, k) & p(n, k)\\ \hline \end{array} \]p(n + k, k)：把每行之前都加一个球，则 \(k\) 个盒子都不为空
CF961G Partitions
题意：
给出 \(n\) 个物品，每个物品有一个权值 \(w_i\)。
定义一个集合 \(S\) 的权值 \(W(S)=|S|\sum\limits_{x\in S}w_x\)。
定义一个划分的权值为 \(W'(R)=\sum\limits_{S\in R}W(S)\)。
求将 \(n\) 个物品划分成 \(k\) 个集合的所有方案的权值和。答案对 \(10^9+7\) 取模。
\(n,k\le2\times10^5\)，\(w_i\le10^9\)。
感性理解，每个数的贡献是相同的，所以答案一定是 \(P\cdot \sum a_i\) 的形式。
枚举当前元素所在集合大小。
\[\begin{aligned} P &= \sum_{i = 1}^ni\cdot \begin{pmatrix}n - 1\\i - 1\end{pmatrix}\begin{Bmatrix}n - i\\k - 1\end{Bmatrix} &\text{从剩下 } n - 1 \text{ 个里选出在当前集合的，再划分其余的 }n - i \text{个。}\\ \\ &= \sum_{i = 1}^ni\cdot \dfrac{(n - 1)!}{(i - 1)!(n - i)!}\sum_{j = 0}^{k - 1}(-1)^j\dfrac{(k - j - 1)^{n - i}}{j!(k - j - 1)!}\\ \\ &= \sum_{j = 0}^{k - 1}(-1)^j\dfrac{1}{j!(k - j - 1)!}\sum_{i = 1}^ni\cdot \dfrac{(n - 1)!(k - j - 1)^{n - i}}{(i - 1)!(n - i)!}\\ \end{aligned} \]单独计算后面一个求和式，把 \(k - j - 1\) 当作常数 \(t\)。
则
\[\begin{aligned} \sum_{i = 1}^ni\cdot \dfrac{(n - 1)!t^{n - i}}{(i - 1)!(n - i)!} &=\sum_{i = 1}^n\dfrac{(n - 1)!t^{n - i}}{(i - 1)!(n - i)!}\cdot (i + 1 - 1)\\ \\ &=\sum_{i = 1}^n\dfrac{(n - 1)!t^{n - i}}{(i - 1)!(n - i)!}\cdot (i - 1 + 1)\\ \\ &=(n- 1)\sum_{i = 1}^n\dfrac{(n - 2)!}{(i - 2)!(n - i)!}\cdot t^{n - i} + \sum_{i = 1}^n\dfrac{(n - 1)!}{(i - 1)!(n - i)!}\cdot t^{n - i}\\ \\ &=(n- 1)\sum_{i = 1}^n\begin{pmatrix}n - 2\\n- i\end{pmatrix}\cdot t^{n - i} + \sum_{i = 1}^n\begin{pmatrix}n - 1\\n- i\end{pmatrix}\cdot t^{n - i}\\ \\ &=(n- 1)(t + 1)^{n - 2} + (t + 1)^{n - 1} \end{aligned} \]时间复杂度 \(O(n\log n)\)。
还有一种更为精巧的解法：
考虑 \(w_i\) 会对答案产生多少次贡献？
在一个大小为 \(|S|\) 的集合中，\(w_i\) 贡献 \(|S|\) 次，等效于集合中每一个元素都使 \(w_i\) 产生一次贡献。
分两部分讨论
-
自己使自己的产生的贡献，显然每一种划分产生一次，共 \(\begin{Bmatrix}n\\k\end{Bmatrix}\) 次。
-
其他元素使自己的产生的贡献，把其余 \(n - 1\) 个球划分好 \(k\) 个集合，对于每种划分，当前元素可以任选一个集合放进去，因此 \(n - 1\) 个物品都会有一次贡献，共 \((n - 1)\begin{Bmatrix}n - 1\\k\end{Bmatrix}\)。
综上 \(P = \begin{Bmatrix}n\\k\end{Bmatrix} + (n - 1)\begin{Bmatrix}n-1\\k\end{Bmatrix}\)。