多项式

偏工具性质。

FFT / NTT

原理比较复杂先咕掉，反正是一个 O(n\log n) 算多项式卷积的东西。

$\rm NTT$ 取模，对模数有特殊要求，若模数 $p=k\cdot 2^t+1$，则只能支持 $n\le2^t$ 的卷积，比 FFT 快。 ## 求导 / 积分 常用的求导： $(x^n)'=nx^{n-1} \ln'(x)=\dfrac 1x (e^x)'=e^x (a^x)'=a^x\ln a (\log_a x)'=\dfrac {1}{x\ln a}

以及运算法则：

加减：

(f(x)+g(x))'=f'(x)+g'(x) (f(x)-g(x))'=f'(x)-g'(x)

乘法：

(f(x)g(x))'=f(x)g'(x)+f'(x)g(x)

复合：

(f(g(x)))'=f'(g(x))\cdot g'(x)

泰勒展开

F(x)=\sum_{i=0}\frac {F^{(i)}(x_0)}{i!}(x-x_0)^i

大概可以理解为在 x_0 处模拟 F(x) 的值，值的变化趋势，变化趋势的变化趋势，...

牛顿迭代法

若 f(G_0(x))\equiv 0\pmod {x^\frac n2},f(G(x))\equiv 0\pmod {x^n}，

则有

G(x)\equiv G_0(x)-\frac {f(G_0(x))}{f'(G_0(x))}\pmod {x^n}

证明：

将在 f(G(x)) 在 G_0(x) 处泰勒展开，得到：

f(G(x))=\sum_{i=0}\frac {f^{(i)}(G_0(x))}{i!}(G(x)-G_0(x))^i

不难发现 G_0(x)\equiv G(x)\pmod {x^\frac n2}，所以 G(x)-G_0(x) 的前 \frac n2 项都是 0，这也就意味着 (G(x)-G_0(x))^k 在 k\ge2 时模 x^n 意义下也是 0，于是将上式化为：

f(G(x))\equiv f(G_0(x))+\frac {f'(G_0(x))}{1!}(G(x)-G_0(x))\pmod {x^n}

推推式子：

0\equiv f(G_0(x))-G_0(x)f'(G_0(x))+G(x)f'(G_0(x))\pmod {x^n} G(x)\equiv G_0(x)-\frac {f(G_0(x))}{f'(G_0(x))}\pmod {x^n}

多项式求逆

即已知 F(x)，求 G(x)，使得

G(x)F(x)\equiv 1\pmod {x^n}

考虑一个迭代倍增的过程：先求出模 x^t 意义下的答案，用这个答案求出模 x^{2t} 意义下的答案，然后令 t\gets 2t，在求下一步，一直倍增到 t\ge n 结束。

在 t=1 时答案是逆元。接下来描述一个由模 x^{\frac t2} 的答案推出模 x^t 时的答案的过程。

考虑已求出 \bmod~x^{\frac t2} 下的答案，即为 G_0(x)。

于是有：

F(x)G_0(x)\equiv 1\pmod {x^\frac t2} F(x)G_0(x)-1\equiv 0\pmod {x^\frac t2}

两边平方（此时模数同样平方），得：

(F(x)G_0(x)-1)^2\equiv 0\pmod {x^t} (F(x)G_0(x))^2-2F(x)G_0(x)\equiv -1\pmod {x^t} F(x)(2G_0(x)-F(x)G_0^2(x))\equiv 1\pmod {x^t}

所以有：

G(x)\equiv 2G_0(x)-F(x)G_0^2(x)\equiv G_0(x)(2-F(x)G_0(x))\pmod {x^t}

依次迭代即可。复杂度 O(n\log n)。

多项式求 ln / exp

求 F(x)，使得

F(x)=\ln G(x)

定义 f(x)=\ln x

则

F(x)=f(G(x))

两边求导，得：

F'(x)=f'(G(x))\cdot G'(x) F'(x)=\frac {G'(x)}{G(x)}

于是求导，求逆，卷积，积分，完了。

求 F(x)，使得

F(x)=e^{G(x)}

求 \ln，得

\ln F(x)=G(x)

于是有 \ln F(x)-G(x)=0

令 f(F(x))=\ln F(x)-G(x)，那么 f'(F(x))=\frac {1}{F(x)}（G(x) 看作常数求导后没了）。

带入牛顿迭代，不妨设已求出 F_0(x)，则得：

F(x)\equiv F_0(x)-\frac {f(F_0(x))}{f'(F_0(x))}\pmod {x^n} F(x)\equiv F_0(x)\cdot (1-\ln F_0(x)+G(x))\pmod {x^n}

套用模板，依次迭代，即可。

> 感觉牛迭的 $\exp$ 没有半在线卷积求 $\exp$ 来的划算（难写 + 慢） ## 多项式次幂 考虑 $F^k(x)\bmod {x^n}$。 先求出 $\ln F(x)$，将其系数都乘 $k$，再 $\exp$ 回去，就行了。大常数 $O(n\log n)$。优势是可以支持 $k$ 非整数的情况。 ## 多项式开根 已知 $F(x)$，求 $G(x)$，使得 $G^2(x)=F(x)$。 令 $f(G(x))=G^2(x)-F(x)$。 即求一个 $G(x)$ 使得 $f(G(x))=0$，牛迭搞一搞吧。初始的 $G(x)$ 是二次剩余。 推出来最终式子： $$G(x)=\frac {G_0^2(x)+F(x)}{2G_0(x)}$$ 复杂度 $O(n\log n)$。 ## 任意模数 有的时候 $\rm NTT$ 的模数可能不是 $998244353$ 一类的 $\rm NTT$ 模数，这时需要使用任意模数多项式乘法。 两种实现： 三模 $\rm NTT$ 或拆系数 $\rm FFT$。 所谓三模 $\rm NTT$，就是选 $998244353,1004535809,469762049$ 三个模数分别 $\rm NTT$，此时精度可达 $10^{26}$ 左右，可以通过中国剩余定理合并出答案，再对给定模数取模即可。常数很大（$9$ 次 $\rm NTT$），且需要 `__int128`，慎用。 拆系数 $\rm FFT$ 使用另一种套路，由于数很大跑裸的 $\rm FFT$ 精度炸飞，于是把系数拆成两部分分别计算。 假设要计算 $F*G$。 令 $F_i=a_i\cdot 2^{15}+b_i,G_i=A_i\cdot 2^{15}+B_i$。 于是 $F*G=2^{30}aA+2^{15}(aB+Ab)+bB$。 所以考虑计算 $a,b,A,B$ 的卷积，由于值域缩小一半，可以保证 $\rm FFT$ 的精度。 但这样是八次 $\rm FFT$，还不如三模 $\rm NTT$ 跑得快。 注意到 $\rm FFT$ 的操作支持两个复多项式卷积，于是令 $P=a+bi,Q=A+Bi,P_0=a-bi$。 然后有 $T_1=P*Q=aA-bB+(aB+Ab)i,T2=P_0*Q=aA+bB+(aB-Ab)i$。 加减就能求得 $aA,aB,Ab,bB$。 三次 $\rm DFT$ 和两次 $\rm IDFT$，共 $5$ 次 $\rm FFT$，比三模 $\rm NTT$ 快得多。有时需要用 `long double`。 ~~出任意模数的都是（）（）~~ ## 封装： ```cpp //mod 998244353,1004535809,469762049 struct poly { const db pi = acos(-1); struct cpx { db x, y; friend cpx operator * (const cpx & a, const cpx & b) { return (cpx){a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x}; } friend cpx operator + (const cpx & a, const cpx & b) { return (cpx){a.x+b.x, a.y+b.y}; } friend cpx operator - (const cpx & a, const cpx & b) { return (cpx){a.x-b.x, a.y-b.y}; } }w[N]; void FFT (cpx f[], int n, int op) { for (int i = 1;i < n;i++) if (tax[i] > i) swap(f[tax[i]], f[i]); w[0] = (cpx){1, 0}; for (int l = 1;l < n;l <<= 1) { cpx W = (cpx){cos(pi/l), sin(pi/l)*op}; for (int i = l-2;i >= 0;i -= 2) w[i+1] = (w[i] = w[i>>1])*W; for (int i = 0;i < n;i += (l<<1)) { for (int j = 0;j < l;j++) { cpx x = f[i|j], y = w[j]*f[i|j|l]; f[i|j] = x+y; f[i|j|l] = x-y; } } } if (op == -1) for (int i = 0;i < n;i++) f[i] = (cpx){floor(f[i].x/n+0.5), floor(f[i].y/n+0.5)}; } ll qpow (ll x, ll y = mod-2) { ll res = 1; while (y) { if (y&1) res = res*x%mod; x = x*x%mod; y >>= 1; } return res; } const int G = 3, Gi = qpow(3); int tax[N]; void init (int n) { for (int i = 1;i < n;i++) tax[i] = (tax[i>>1]>>1)|(i&1 ? n>>1 : 0); } void NTT (int f[], int n, int op) { for (int i = 1;i < n;i++) if (tax[i] > i) swap(f[tax[i]], f[i]); for (int l = 1;l < n;l <<= 1) { ll W = qpow(op == 1 ? G : Gi, (mod-1)/(l<<1)); for (int i = 0;i < n;i += (l<<1)) { ll w = 1; for (int j = 0;j < l;j++, w = w*W%mod) { int x = f[i|j], y = f[i|j|l]*w%mod; f[i|j] = (x+y)%mod; f[i|j|l] = (1ll*x-y+mod)%mod; } } } if (op == -1) for (int i = 0, ni = qpow(n);i < n;i++) f[i] = 1ll*f[i]*ni%mod; } cpx ma[N], mb[N], mc[N]; void MTT (int f[], int g[], int ans[], int n) { init(n); for (int i = 0;i < n;i++) ma[i].x = f[i]>>15, ma[i].y = f[i]&32767, mb[i].x = g[i]>>15, mb[i].y = g[i]&32767, mc[i].x = f[i]>>15, mc[i].y = -(f[i]&32767); FFT(ma, n, 1); FFT(mb, n, 1); FFT(mc, n, 1); for (int i = 0;i < n;i++) ma[i] = ma[i]*mb[i], mc[i] = mc[i]*mb[i]; FFT(ma, n, -1); FFT(mc, n, -1); for (int i = 0;i < n;i++) { int x = (ll)floor((ma[i].x+mc[i].x)/2+0.5)%mod, y = (ll)floor((ma[i].y+mc[i].y)/2+0.5)%mod, p = (ll)floor((mc[i].x-ma[i].x)/2+0.5)%mod, q = (ll)floor((ma[i].y-mc[i].y)/2+0.5)%mod; ans[i] = ((1ll<<30)%mod*x%mod+(1ll<<15)%mod*(y+q)%mod+p)%mod; ans[i] = (ans[i]+mod)%mod; } } int t[N]; void inv (int f[], int g[], int n) { g[0] = qpow(f[0]); for (int i = 1;i < (n<<1);i++) g[i] = 0; for (int l = 1;l < n;l <<= 1) { int tl = l<<1; for (int i = 0;i < tl;i++) t[i] = f[i]; for (int i = tl;i < (tl<<1);i++) t[i] = 0; tl <<= 1; init(tl); NTT(t, tl, 1); NTT(g, tl, 1); for (int i = 0;i < tl;i++) g[i] = 1ll*g[i]*(2-1ll*g[i]*t[i]%mod+mod)%mod; NTT(g, tl, -1); for (int i = l+l;i < tl;i++) g[i] = 0; } } void dev (int f[], int g[], int n) { for (int i = 1;i < n;i++) g[i-1] = 1ll*f[i]*i%mod; g[n-1] = 0; } void inv_dev (int f[], int g[], int n) { for (int i = 1;i < n;i++) g[i] = f[i-1]*qpow(i)%mod; g[0] = 0; } int a[N], b[N]; void ln (int f[], int g[], int n) { for (int i = 0;i < (n<<1);i++) b[i] = a[i] = 0; inv(f, a, n); dev(f, b, n); n <<= 1; init(n); NTT(a, n, 1); NTT(b, n, 1); for (int i = 0;i < n;i++) a[i] = 1ll*a[i]*b[i]%mod; NTT(a, n, -1); n >>= 1; inv_dev(a, g, n); } int c[N], d[N]; void exp (int f[], int g[], int n) { g[0] = 1; for (int i = 1;i < (n<<1);i++) g[i] = 0; for (int l = 1;l < n;l <<= 1) { int tl = l<<1; for (int j = 0;j < (tl<<1);j++) c[j] = d[j] = 0; ln(g, c, tl); d[0] = 1; for (int i = 0;i < tl;i++) d[i] = (d[i]-c[i]+f[i]+mod)%mod; tl <<= 1; init(tl); NTT(d, tl, 1); NTT(g, tl, 1); for (int i = 0;i < tl;i++) g[i] = 1ll*g[i]*d[i]%mod; NTT(g, tl, -1); tl >>= 1; for (int i = tl;i < (tl<<1);i++) g[i] = 0; } } int sa[N], sf[N]; void sqrt (int f[], int g[], int n) { g[0] = 1; g[1] = g[2] = g[3] = 0; for (int l = 1;l < n;l <<= 1) { int tl = l<<1; inv(g, sa, tl); for (int i = 0;i < tl;i++) sa[i] = sa[i]*qpow(2)%mod; for (int i = 0;i < tl;i++) sf[i] = f[i]; for (int i = tl;i < (tl<<2);i++) sf[i] = 0; tl <<= 2; init(tl); NTT(g, tl, 1); NTT(sa, tl, 1); NTT(sf, tl, 1); for (int i = 0;i < tl;i++) g[i] = (1ll*g[i]*g[i]%mod+sf[i])*sa[i]%mod; NTT(g, tl, -1); tl >>= 1; for (int i = tl;i < (tl<<2);i++) g[i] = 0; } } }poly; ``` $\large{\rm FWT}

除了正常的多项式卷积之外，还有一种常用的位运算卷积。

\sum_i\sum_j F_iG_j=H_{i*j} （这里的 $*$ 指某种位运算） 我们仿照 $\rm FFT$ 搞这个东西，先转成可以点积的形式，然后再点乘，再转回去。 但我们不知道怎么转点积，不妨设 $i$ 向 $j$ 的贡献为 $c(j,i)$。 即：${\rm FWT}(F)_i=\sum\limits_{j=0}F_jc(i,j)

经过一系列（我不会）的推导得到，若我们要支持某种 * 的位运算，可以令 c(i,j) 为 c(i_0,j_0)c(i_1,j_1)...，即二进制下每一位的 c 的积，而 c 又只需满足 c(i,j)c(i,k)=c(i,j*k) 即可。

用这个东西即可做出 \rm FWT。

其实可以背代码

void FWT (int *f, int n, const int c[2][2]) {
    for (int l = 1;l < n;l <<= 1) {
        for (int i = 0;i < n;i += l+l) {
            for (int j = 0;j < l;j++) {
                ll x = f[i|j], y = f[i|j|l]; 
                f[i|j] = (x*c[0][0]+y*c[0][1])%mod, f[i|j|l] = (x*c[1][0]+y*c[1][0])%mod; 
            }
        }
    }
}

可以看到，关键在于矩阵 c 的构造。

矩阵表：

Cor =\left\{\begin{matrix}1 &0\\1&1\end{matrix}\right\}

tip：cor(i,j)=[i \operatorname{ and } j=j]。

iCor=\left\{ \begin{matrix} 1&0\\-1 &1\end{matrix} \right\} Cand=\left\{ \begin{matrix} 1 &1\\0&1\end{matrix}\right\}

tip：cand(i,j)=[i \operatorname{ and} j=i]。

iCand=\left\{\begin{matrix} 1&-1\\0&1\end{matrix}\right\} Cxor=\left\{\begin{matrix} 1 &1\\1&-1\end{matrix}\right\}

tip：cxor(i,j)=(-1)^{|i \operatorname{and}j|}

iCxor=\left\{\begin{matrix} 0.5&0.5\\0.5&-0.5\end{matrix}\right\}

若表达式转点积，就传 C*（* 为位运算名称），点积转表达式，就传 iC*。

可以看到 \rm FWT 的变换不依赖于模数。

生成函数

注意，在生成函数中，x 代表的意义并非未知数，也不具有任何值，而仅仅是一个代数对象。

\large\rm OGF

普通生成函数。

表示为 F(x)=\sum\limits_{i=0}a_ix^i。

其实是把我们要求的东西用多项式（？）表示，通过 x 的指数加以区分。

例如，对于序列 a=\left<1,1,1,... \right>，F(x)=\sum\limits_{i=0}x^i。

对于序列 a=\left<1,p,p^2,...\right>，F(x)=\sum\limits_{i=0}p^ix^i。

重新回过头看 a=\left<1,1,1,...\right> 的生成函数 F(x)=\sum\limits_{i=0}x^i，发现 xF(x)=\sum\limits_{i=0}x^{i+1}=\sum\limits_{i=1}x^i，于是有 F(x)-xF(x)=1，故 F(x)=\dfrac 1{1-x}，称这个东西为 F(x) 的封闭形式。

同理，对于 a=\left<1,p,p^2,...\right>，其生成函数 F(x) 有 F(x)=pxF(x)+1，所以 F(x)=\dfrac 1{1-px}。或令 px 代换 F(x)=\sum\limits_{i=0}x^i 的 x 也可以得到同样的结论。

其原理基本类似，运用错位即可。

例如斐波那契数列 fib。

其生成函数 F(x)=\sum\limits_{i=0}fib_ix^i。

由于 fib_i=fib_{i-1}+fib_{i-2}，于是考虑错位：

F(x)=\sum\limits_{i=0}fib_ix^i xF(x)=\sum\limits_{i=0}fib_ix^{i+1}=\sum\limits_{i=1}fib_{i-1}x^i x^2F(x)=\sum\limits_{i=0}fib_ix^{i+2}=\sum\limits_{i=2}fib_{i-2}x^i

令 F(x) 减去 xF(x)+x^2F(x)，除常数项和一次项外的系数全部抵消，于是有：

F(x)=xF(x)+x^2F(x)+fib_0+fib_1x=xF(x)+x^2F(x)+x F(x)=\frac x{1-x-x^2}

或者一种更直观的形式（中间加号为了美观省略）：

\begin{array}{cc}F(x)=& fib_0&fib_1x&fib_2 x^2&fib_3x^3&...\\xF(x)= &&fib_0x &fib_1x^2& fib_2x^3&...\\x^2F(x)=&&&fib_0x^2&fib_1x^3&...\end{array}{}

可以更显然地得到 F(x)=xF(x)+x^2F(x)+x 的结论。

至此我们得到了 F(x) 的封闭形式。

一般来说，封闭形式有两种作用：求递推式或通项。

接下来以 fib 为例利用封闭形式，得到的通项。

不妨设 \dfrac A{x-a}+\dfrac B{x-b}=\dfrac x{1-x-x^2}。

通分后对应分子分母的系数即可解得 A,B,a,b。

我们要求的 fib_n 就是 [x^n](\dfrac A{x-a}+\dfrac B{x-b})。

推一推式子：

[x^n](-(\frac {\frac Aa}{1-\frac xa}+\frac {\frac Bb}{1-\frac xb}))

将下面的封闭形式展开：

[x^n](-(\frac Aa(\sum_{i\ge0}\frac 1{a^i}x^i)+\frac Bb(\sum_{i\ge0}\frac 1{b^i}x^i)))

提出来 n 次项系数，得到

-(\frac A{a^{n+1}}+\frac {B}{b^{n+1}})

于是带入 a,b,A,B 即可得到通项。

考虑两个 \rm OGF 相乘，不难发现它的本质是加法卷积。

因此它代表的组合意义是顺序拼接（联想 dp 背包那一套理论）。

以经典的付钱问题来想：

你有 2,3,5 三种面额的硬币，每种硬币可以无限使用，求用这些硬币付 n 元的方案。

首先考虑用三种面额的硬币各自拼接 n 元的生成函数，不难得到：

F_2(x)=\sum\limits_{i\ge0}x^{2i}=\dfrac {1}{1-x^2} F_3(x)=\sum\limits_{i\ge0}x^{3i}=\dfrac 1{1-x^3} F_5(x)=\sum\limits_{i\ge0}x^{5i}=\dfrac 1{1-x^5}

那么 [x^n]F_2(x)F_3(x)F_5(x) 即为所求。

例题 [国家集训队] 整数的lqp拆分

定义一种方案 a 的权值 v_a 为 \prod fib_{a_i}。

求 \sum\limits_a v_a[\sum a_i=n]。

令 F(x)=\dfrac x{1-x-x^2} 为 fib 的生成函数，设答案的生成函数为 G(x)，那么拼出 n 的答案即为 [x^n]G(x)，不难得到答案的生成函数G(x)=[x^n]\sum\limits_{i=1}F^i(x)。

也通过类似转封闭形式的操作，得到 G(x)=\dfrac {F(x)}{1-F(x)}，将 F(x)=\dfrac x{1-x-x^2} 带入推式子，最后得出 G(x)=\dfrac x{1-2x-x^2}，通过上面的技巧求通项，得到：

\begin{cases}a=-1+\sqrt2\\b=-1-\sqrt2\\A=\frac {-2+\sqrt2}4\\B=\frac {-2-\sqrt2}4\end{cases}

套用上面的式子，进行代数化简，得到 [x^n]G(x)=\frac {(\sqrt2+1)^n-(\sqrt2-1)^n}{2\sqrt2}。二次剩余求 \sqrt 2 即可。

有时答案可以 dp 出来，但是复杂度过高，此时可以令 F(x) 表示 dp 数组模拟转移，使用多项式科技快速求值。

例题 The Child and Binary Tree

不难发现有转移方程：

f_m=\sum_{i=1}^n\sum_{j=1}^{m-c_i}f_j\cdot f_{m-c_i-j}

暴力转移复杂度裂开。（特别注意，我们令 f_0=1）。

令 F=\left<f_0, f_1,...\right>，模拟推导过程，有 F(x)=\sum\limits_{i=1}^n x^{c_i}F^2(x)+f_0=\sum\limits_{i=1}^n x^{c_i}F^2(x)+1

不妨令 G(x)=\sum\limits_{i=1}^n x^{c_i}，则 F(x)=G(x)F^2(x)+1，解方程得到 F(x)=\dfrac{1\pm\sqrt{1-4G(x)}}{2G(x)}，出现两种解，需要舍去一个，思考一下，将 x=0 带入式子，应该可以得到 F(0)=f_0=1，而 G(0)=0，式子化为 \dfrac{1\pm 1}0=1（很不规范的写法，但为了方便就这样写），显然取 -（如果取 + 似乎成了 \infty），于是得到 F(x)=\dfrac {1-\sqrt{1-4G(x)}}{2G(x)}，直接多项式板子搞搞就行了，也可以化为 \dfrac 2{1+\sqrt {1-4G(x)}}，做到更优秀的常数。

\large \rm EGF

指数型生成函数。

形式：F(x)=\sum\limits_{i=0}a_i\dfrac{x^i}{i!}。

仍然探讨对于一些数列的 \rm EGF 的封闭形式，对于 a=\left<1,1,...\right>，可以得到其 \rm EGF F(x)=\sum_{i=0}\dfrac {x^i}{i!}=e^x，什么原理？将 e^x 进行泰勒展开即可得到左式。同理，对于 a=\left<1,p,p^2,...\right> 有 F(x)=\sum\limits_{i=0}p^i \dfrac {x^i}{i!}=e^{px}。

还有一些别的 \rm EGF 的封闭形式：

\left<1,-1,1,-1,...\right>$，$F(x)=e^{-x}

和 \left<1,1,1,...\right> 加减和得到另外两个常用的：

\left<1,0,1,0,...\right>,F(x)=\dfrac {e^x+e^{-x}}{2} \left<0,1,0,1,...\right>,F(x)=\dfrac {e^x-e^{-x}}{2}

相比 \rm OGF，\rm EGF 的积的意义复杂一些。

F(x)G(x)=\sum\limits_{i=0}(\sum\limits_j\dfrac{f_j}{j!} \dfrac{g_{i-j}}{(i-j)!})x^i=\sum\limits_{i=0} (\sum\limits_{j=0}^i \binom{i}{j}f_jg_{i-j})\dfrac {x^i}{i!}

注意到 \binom ij f_jg_{i-j}，它其实是从 i 个数中选出 j 个分配给 f，再将剩下的分配给 g，所以 \rm EGF 的积是带编号的拼接。

还有一个重要性质，我们考虑对于 \rm EGF F(x)，e^{F(x)} 的含义。

展开一下 e^{F(x)}=\sum\limits_{i\ge 0}\dfrac {F^i(x)}{i!}，F^i(x) 的含义就是将 i 个 F(x) 集合拼接在一起，除掉了 i! 相当于将不同集合之间的先后顺序废掉，所以，若我们用 F(x) 表示单个部分的 \rm EGF，那么 e^{F(x)} 就代表着由若干个相同部分组成的整体的 \rm EGF。

注意：由于在实战中多项式的系数直接除掉了阶乘，最后统计答案时记得乘回来。

例题 集合划分计数

求将 n 个不同的小球放入若干个相同盒子的方案。

显然可以求第二类 stirling 数，显然会 T 飞。

往 \rm EGF 方面联想，考虑先求出单个盒子的 \rm EGF，不难发现，F(x)=\sum\limits_{i\ge1}\dfrac {x^i}{i!}=e^x-1。那么若干个相同盒子的方案即为 [x^n]e^{F(x)}=[x^n]e^{e^x-1}。多项式 \exp 即可。

例题 自然数幂和

和 \rm EGF 本身的组合意义关系不大，起到中间推导的作用吧。

令 S_n(k)=\sum\limits_{i=0}^ni^k，我们要求的是 S_n(1),S_n(2),...,S_n(m)。

注意到序列 \left<1,p,p^2,...\right> 的 \rm EGF F_p(x)=\sum\limits_{i=0}p^i\dfrac{x^i}{i!}=e^{px}。

我们有 S_n(k)=\left[\dfrac{x^k}{k!}\right]\sum\limits_{i=0}^n F_i(x)=[\dfrac{x^k}{k!}]\sum\limits_{i=0}^n e^{ix}=\left[\dfrac {x^k}{k!}\right]\dfrac {e^{(n+1)x}-1}{e^x-1}。

令 G(x)=\dfrac {e^{(n+1)x}-1}{e^x-1}，把 G(x) 算出来就行，注意到分母常数项是 0 求不了逆，但分母常数项也是 0，上下同时除掉 x，把下面的东西求逆再卷积就行。

用 S_n(k)=\left[\dfrac {x^k}{k!}\right]G(x) 即可算出自然数幂和。

练习题

Thief in a Shop

注意到多个物品的总价值是价值和的形式，将价值提到指数上，我们得到：

F(x)=\sum\limits_{1\le i\le n} x^{a_i}

而选择 k 个物品自然是 F^k(x)。

于是寻找 F^k(x) 中系数不为 0 的项的指数即可。

[Substring Search](https://www.luogu.com.cn/problem/CF1334G) 用 $\rm FFT$ 匹配字符串。 先考虑如何使用 $\rm FFT$ 匹配普通的两个字符串，如果我们要查看 $T,S$ 是否相等，一个好的方法是查看 $v=\sum\limits_{1\le i\le |T|}(T_i-S_i)^2=\sum\limits_{1\le i\le |T|} T_i^2+S_i^2-2T_iS_i$ 是否为 $0$。平方和的处理是容易的，$T_iS_i$ 的项可以把 $S$ 倒过来跑卷积。 回到本题。 我们称原来的 $s$ 为 $s_0$，将 $s$ 中的字符置换后的新字符串称为 $s_1$。 若我们用 $t$ 匹配 $s$，只需让 $t_j$ 和 ${s_0}_i$ 和 ${s_1}_i$ 中的一个匹配即可。于是可以构造一个新的数 $v=\sum\limits_{1\le i\le t}(t_i-{s_0}_i)^2(t_i-{s_1}_i)^2$ 即可。 拆开卷卷就行了。给每个字符赋一个随机权值再用 $\rm NTT$ 才行。 [Binary Table](https://www.luogu.com.cn/problem/CF632E) $n,m$ 差距很大，而 $n\le20$，自然想到枚举每一行是否翻转，之后列就能轻易判断，然而复杂度 $O(2^nnm)$，比较寄。 考虑把每一列当成一个 $n$ 位二进制数看，记为 $x_1,x_2,...$，设 $v_i$ 表示当这一列为 $i$ 时能得到的最小 $1$ 的数量。 枚举之后的翻转可以看做每一列同时 $\rm xor$ 某个数，事实上“某个数”取在 $[0,2^n)$。 我们同时令 $v_i$ 分别向 $v_{i \operatorname{xor} x_1},v_{i \operatorname{xor} x_2},...$ 作贡献，最终的 $v_k$ 就是在行翻转状态为 $k$ 时的答案。 于是 $\rm xor$ 下的 $\rm FWT$ 卷积一下即可。 [The Three Little Pigs](https://www.luogu.com.cn/problem/CF1548C) 假设我们取走 $k$ 个球，那么方案数：$\sum\limits_{i=1}^n\dbinom{3i}{k}$。 构造生成函数：$F(x)=\sum\limits_{i=0}\sum\limits_{j=1}^n\dbinom{3j}{i}x^i=\sum\limits_{j=1}^n\sum\limits_{i=0}\dbinom{3j}{i}x^i=\sum\limits_{j=1}^n(x+1)^{3j}=\dfrac{(x+1)^{3(n+1)}-(x+1)^{3}}{(x+1)^3-1}$。 暴力跑多项式除法，$O(n)$ 带走。 [[CTS2019] 珍珠](https://www.luogu.com.cn/problem/P5401) 概率乘 $D^n$ 变能实现的方案数。由于 $2$ 个相同颜色可以做出 $1$ 的贡献，枚举出现奇数次的颜色个数，设为 $k$，则做出贡献当且仅当 $\lfloor \dfrac{n-k}2\rfloor\ge m$，来一波二项式反演套路，于是变为钦定 $k$ 个颜色出现奇数次，其余随意的方案。 钦定 $k$ 个颜色出现单数次，其余随意，我们通过 $\rm EGF$ 来计算，先计算出单色的 $\rm EGF$ 是容易的，若有单数限制，则 $F(x)=\sum\limits_{i=0}\dfrac {x^{2i+1}}{(2i+1)!}=\dfrac {e^x-e^{-x}}{2}$，随意则为 $G(x)=\sum\limits_{i=0}\dfrac {x^i}{i!}=e^x$，卷在一块，得到我们要求的为 $\left[\dfrac {x^n}{n!}\right]\dbinom{D}{k}F^k(x)G^{D-k}(x)$。 接下来开始推式子： $$\left[\dfrac{x^n}{n!}\right]\dbinom DkF^k(x)G^{D-k}(x)= \left[\dfrac {x^n}{n!}\right] \dbinom{D}{k}(\dfrac{e^x-e^{-x}}{2})^ke^{(D-k)x}$$ 把 $k$ 次幂的二项式展开，得： $$\left[\dfrac {x^n}{n!}\right] \frac {\binom{D}{k}}{2^k} e^{(D-k)x}\left(\sum_{i=0}^k \binom{k}{i}e^{xi}(-e^{-x})^{k-i} \right)$$ 把 $e$ 的指数合并一下 $$\left[\dfrac {x^n}{n!}\right] \frac {\binom{D}{k}}{2^k} \left(\sum_{i=0}^k \binom{k}{i} (-1)^{k-i}e^{x(D-2(k-i))} \right)$$ 由对称性： $$\left[\dfrac {x^n}{n!}\right] \frac {\binom{D}{k}}{2^k} \left(\sum_{i=0}^k \binom{k}{i} (-1)^{i}e^{x(D-2i)} \right)$$ 由于 $\left[\dfrac{x^n}{n!}\right]e^{kx}=k^n$，于是提取系数： $$\frac {\binom{D}{k}}{2^k} \left(\sum_{i=0}^k \binom{k}{i} (-1)^{i}(D-2i)^n \right)$$ 拆一拆组合数： $$\frac{D!}{(D-k)!2^k}\sum_{i=0}^k \frac{(D-2i)^n(-1)^i}{i!}\cdot \frac{1}{(k-i)!}$$ 卷一下就行了。 [calc](https://www.luogu.com.cn/problem/P5850) 考虑到互不相等的限制，只需枚举其中的元素，最后乘 $n!$ 即可。 那么相当于从 $1,2,...,k$ 中选出 $n$ 个数相乘的所有方案之和。 容易得到其生成函数 $F(x)=\prod\limits_{i=1}^k (1+ix)$，选 $n$ 个数的答案即为 $[x^n]F(x)$。 然后套路地求 $\ln$，变为： $$\ln F(x)=\sum_{i=1}^k\ln(1+ix)$$ 对 $\ln(1+px)$ 进行同样套路的展开，求导： $$\dfrac {p}{1+px}$$ 注意到 $\dfrac {1}{1+px}=\sum\limits_{i=0}(-1)^ip^ix^i$，带入原式： $$p\sum_{i=0}(-1)^ip^ix^i=\sum_{i=0}(-1)^ip^{i+1}x^i$$ 积回去： $$\sum_{i=1}(-1)^{i-1}\frac{p^i}{i}x^i$$ 带回最初式子，有： $$\begin{array}{c}\ln F(x)&=&\sum\limits_{i=1}^k\sum\limits_{j=1}(-1)^{j-1}\dfrac {i^j}{j}x^j\\&=& \sum\limits_{j=1}(\sum\limits_{i=0}^ki^j)\dfrac{(-1)^{j-1}}{j}x^j\end{array}{}$$ 自然数幂搞搞，把多项式求出来，再跑 $\exp$，$O(n\log n)$。 [Tree Coloring](https://codeforces.com/contest/1613/problem/F) 挺有意思的一个题。 对父子权值的限制很难搞，考虑将它容斥掉。接下来考虑钦定 $k$ 个结点的父亲值为它的结点权值加一。注意到每钦定一个结点实际上是将两个结点的权值联系在一起，于是钦定 $k$ 个结点最终会形成 $n-k$ 个互不相干的值域块，看起来答案是 $\binom {n-1}k(n-k)!$。 但仔细想有个问题，如果我们钦定的两个结点拥有相同的父亲，那么它们的权值相等，不符合限制 $2$，注意到每个结点最多被钦定 $1$ 个儿子，用多项式来算。 设 $i$ 有 $d_i$ 个儿子，那么令 $F_i(x)=1+d_ix$，由于每个结点选一个儿子的方案数为 $d_i$，于是 $(n-k)![x^k]\prod\limits_{1\le i\le n}F_i(x)$ 就是我们所求的。 $\prod\limits_{1\le i\le n}F_i(x)$ 可以用分治 $\rm NTT$，复杂度 $O(n\log^2n)$。 [PolandBall and Many Other Balls](https://codeforces.com/problemset/problem/755/G) 先考虑 dp，设 $f_{n,k}$ 为将 $n$ 个球按题意分组后选 $k$ 组的方案，那么有 $f_{n,k}=f_{n-1,k-1}+f_{n-2,k-1}+f_{n-1,k}$。 考虑令 $F_n(x)$ 为 $f_n$ 的生成函数，那么有 $F_n(x)=(1+x)F_{n-1}(x)+xF_{n-2}(x)$。 设矩阵 $G=\left\{\begin{matrix}1+x &1\\ x&0\end{matrix}\right\}$，初始矩阵 $S=\left\{\begin{matrix} 1 &0\\0&0\end{matrix}\right\}$，求出 $S*G^n$ 即可。常数挺大。 [Bandit Blues](https://codeforces.com/problemset/problem/960/G) 挺厉害一个题。 显然可以通过枚举 $n$ 的位置，于是只需统计前缀最大值为 $A$ 的方案。 设 $f_{n,k}$ 为长度为 $n$ 的排列有 $k$ 个前缀最大值的方案数。 每次枚举新加入的最大值转移，有：$f_{n,k}=\sum\limits_{i=1}^n f_{i-1,k}(n-i)!\dbinom{n-1}{i-1}$。 然后发现这个式子没有什么转移的好方法。 $\text {\color{black}A\color{red}NIG}$ 发现可以每次插入最小值，于是有：$f_{n,k}=f_{n-1,k-1}+(n-1)f_{n-1,k}$。这恰好是第一类斯特林数的递推式。（稍加考察可以发现边界条件也是相同的） 于是我们发现 $f_{n,k}=\left[\begin{matrix}n\\k\end{matrix}\right]$。 所以我们要求的答案即：$\sum\limits_{i=1}^n f_{i-1, A-1}f_{n-i, B-1}\dbinom{n-1}{i-1}=\sum\limits_{i=1}^n \left[\begin{matrix} i-1\\A-1\end{matrix}\right] \left[\begin{matrix}n-i\\B-1\end{matrix}\right]\dbinom{n-1}{i-1}$。 接下来我们令 $A\gets A-1,B\gets B-1$。 考虑第一类斯特林数 $\left[\begin{matrix}n\\k\end{matrix}\right]$ 的组合意义为将 $n$ 个数选为 $k$ 个环的方案。于是上式的意义为从 $n-1$ 个数中选出 $i-1$ 个，再将这 $i-1$ 个数选为 $A$ 个环，然后将剩下的 $n-i$ 个数选为 $B$ 个环的方案。而它们的和的意义即为从 $n-1$ 个数中选出 $A+B$ 个环，再从 $A+B$ 个环中选出 $A$ 个的方案数。即 $\left[\begin{matrix}n-1\\A+B\end{matrix}\right]\dbinom{A+B}{A}$。 分治 $\rm NTT$ 搞一下第一类斯特林数就行了。