计数
- 本篇侧重于生成函数方向的计数，不过知识点上是由易到难的（大概
- 一些基础科技内容不会详细提及
组合数
计数里面最基本的部分
1.定义
排列：从\(n\)个物品中选出\(m\)个来，且考虑顺序，方案数记为\(A_n^m\)
组合：从\(n\)个物品中选出\(m\)个来，不考虑顺序，方案数记为\(C_n^m\)，又可记作\(\binom nm\)
（由于在计数题中出现的基本为组合，所以本文内容主要关于组合问题）
2.计算
\[A_n^m=n^{\underline m}=\frac{n!}{(n-m)!}\\ C_n^m=\frac{n!}{m!(n-m)!} \]同时，\(C_n^m\)也可通过公式\(C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\)来计算，证明：考虑分是否选择第\(n\)个来计算。这也是我们的杨辉三角的递推公式，但由于复杂度较大，所以这个公式实际并不常用
3.一些简单的技巧
(1)多重集合
当\(\sum n_i=n\)时，有\(\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots\binom{n_n}{n_n}=\frac{n}{\prod n_i!}\)
证明：拆开就可以了
(2)范德蒙卷积
\[\sum_{i=0}^k\binom ni\binom m {k-i}=\binom {n+m}k \]证明：考虑组合意义，实际就等价于在\(n+m\)个数中选出\(k\)个数的方案数，即\(\binom {n+m}k\)
(3)插板法
把\(n\)个相同的球分为\(m\)个不同的组，每组内至少有一个球，方案数为\(\binom {n-1}{m-1}\)
若每组内可以没有球，则方案数为\(\binom {n+m-1}{m-1}\)
(4)求一列组合数的和
\(\sum_{i=n}^m\binom in=\binom {m+1}{n+1}\)
证明：仍然考虑组合意义，我们不妨令\(\binom in\)表示在前\(i\)个球中任选\(n\)个，然后强制在第\(i+1\)个位置放一个球的方案，那么这个求和式的组合意义相当于是统计第\(n+1\)个球（也就是最后一个球）选择的是第\(n+1\sim m+1\)中每个位置的方案和，这也就是在\(m+1\)个球中任选\(n+1\)个球的方案数
4.二项式定理
(1)普通幂
\[\begin{aligned} (a+b)^n&=\sum_{i=0}^n\binom n ia^ib^{n-i} \end{aligned} \]特别的，当\(a=b=1\)时，有\(\sum_{i=0}^n\binom ni=2^n\)
当\(a=1\)时，考虑到组合数的形式，有生成函数\(F(x)=\sum_{i\ge 0}\binom n ix^i=(1+x)^n\)
由此还能得出多项式定理：
\[(a_1+a_2+...+a_m)^n=\sum_{\sum n_i=n}\frac{n!}{\prod n_i!}\prod a_i^{n_i} \](2)上升/下降幂
\[(a+b)^{\underline n}=\sum_{i=0}^{n}\binom{n}{i}a^{\underline i}b^{\underline {n-i}}\\ (a+b)^{\overline n}=\sum_{i=0}^{n}\binom{n}{i}a^{\overline i}b^{\overline {n-i}} \]只证明第一条
\[\begin{aligned} (a+b)^{\underline n}&=\sum_{i=0}^{n}\binom{n}{i}a^{\underline i}b^{\underline {n-i}}\\ \frac{(a+b)^{\underline n}}{n!}&=\sum_{i=0}^{n}\frac{a^{\underline i}b^{\underline {n-i}}}{i!(n-i)!}\\ \binom{a+b}{n}&=\sum_{i=0}^n\binom{a}{i}\binom{b}{n-i} \end{aligned} \]也就是上文的范德蒙卷积
5.广义二项式定理
我们定义牛顿二项式系数为\(\binom n m=\frac{n(n-1)...(n-m+1)}{m!}\)，其中\(n\in R\)，\(m\)为自然数
那么有：（注意\(a,b,m\)为实数，且\(|\frac ab|<1\)）
\[\begin{aligned} (a+b)^m=\sum_{i=0}^{+\infty}\binom m ia^ib^{m-i} \end{aligned} \]其中，特殊的有（\(m<0\))
\[\begin{aligned} (1+x)^m&=\sum_{i=0}^{+\infty}\binom mix^i\\ \\ (1-x)^m&=\sum_{i=0}^{+\infty}\binom mi(-x)^i\\ &=\sum_{i=0}^{+\infty}(-1)^i\frac{m^{\underline i}}{i!}x^i\\ &=\sum_{i=0}^{+\infty}(-1)^{2i}\frac{(i-m-1)^{\underline i}}{i!}x^i\\ &=\sum_{i=0}^{+\infty}\frac{(i-m-1)^\underline i}{i!}x^i \end{aligned} \]6.k维差分与前缀和
给出一个长度为\(n\)的序列\(a\)，求它的\(k\)阶差分或\(k\)阶后缀和，对\(p=998244353\)取模
其中\(k\le 10^{23333}\)
我们不妨把\(a\)看成一个多项式\(F(x)=\sum a_ix^i\)
那么求其一阶的前缀和的一个方法是，我们将\(F(x)\)卷上一个多项式\(G(x)=\frac{1}{1-x}\)
我们现在要求出\(\frac{1}{(1-x)^k}\)，不妨考虑将其写成\((1-x)^{-k}\)的形式，由广义二项式定理可知道其为
\[(1-x)^{-k}=\sum_{i=0}^{+\infty}\frac{(i+k-1)^\underline i}{i!}x^i \]然后卷就好了
现在要求\(k\)阶差分
同样的，我们有\(G(x)=1-x\)，差分直接\(F(x)\cdot G(x)\)就好了
那么\(k\)阶即为
\[G^k(x)=(1-x)^k=\sum_{i=0}^{+\infty}(-1)^i\frac{k^\underline i}{i!}x^i \]这个就是一个简单的二项式定理，然后中间\(\frac{k^\underline i}{i}\)那一项直接递推即可，那么\(k\)就可以直接\(\mod p\)了
7.\(\binom{2n}{n}\)
这是一个经典的数列，有一个简洁的生成函数形式
我们可以求出\(\binom {n-\frac 12}{n}\)的值
那么考虑这样一个东西\(n^\underline n(n-\frac 12)^{\underline n}\)，我们给每一项都\(\times 2\)来拉大间隙，那么就等于\(\frac{2n^{\underline {2n}}}{2^{2n}}\)
也就是说
\[n^\underline n(n-\frac 12)^{\underline n}=\frac{2n^{\underline {2n}}}{2^{2n}} \]两边同时除以\((n!)^2\)有
\[2^{2n}\times \binom{n-\frac 12}n=\binom{2n}n\\ (-4)^n\times\binom{-\frac 12}{n}=\binom {2n}n\\ \]那么写成生产函数形式有
\[\begin{aligned} \sum_{i=0}\binom{2i}ix^i&=\sum_{i=0}(-4)^i\times \binom{-\frac 12}{i}x^i\\ &=\sum_{i=0}\binom{-\frac 12}{i}(-4x)^i \end{aligned} \]运用广义二项式定理可得其等于\((1-4x)^{-\frac 1 2}\)
8.组合数构造卷积
\[\begin{aligned} i(n-i)&=\binom{n}{2}-\binom{i}{2}-\binom{n-i}{2}\\ ij&=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2} \end{aligned} \]对于出现幂上的乘积时，可以用这个技巧构造卷积
例：
【P6800】Chirp Z-Transform
给定一个\(n\)项多项式\(P(x)\)以及\(c,m\)请计算\(P(c^0),P(c^1),P(c^2)\cdots,P(c^{m-1})\)
对\(998244353\)取模
\(1\le n,m\le 10^6\)
我们直接应用上面第二条柿子
\[\begin{aligned} P(c^t)&=\sum_{i=0}^{n-1}p_ic^{it}\\ &=\sum_{i=0}^{n-1}p_ic^{\binom{i+t}{2}-\binom{i}{2}-\binom{t}{2}}\\ &=c^{-\binom{t}{2}}\sum_{i=0}^{n-1}p_ic^{\binom{i+t}{2}-\binom{i}{2}} \end{aligned} \]可以观察到后面是一个差卷积的形式，于是就做完了
二项式反演
由于去年的课件中各类反演都很齐全，所以这里就只对二项式反演做一些补充
1.反演推论
反演指的是两个函数之间的双向关系，如差分和前缀和
现在我们有一个关系矩阵\(A\)，以及两个函数\(f,g\)
同时\(f=A*g\)，即\(f(n)=\sum_{i=0}^nA_{n,i}g(i)\)
我们现在想要从\(f\)推出\(g\)
不难想到就是两边乘上\(A^{-1}\)
也就是说，反演关系中的两个矩阵互逆
由于一对互逆的矩阵转置后仍然互逆，我们可以得到反演的种种变形
2.二项式反演
(1)壹之型
\[\begin{aligned} f(n)&=\sum_{i=0}^n(-1)^i\binom{n}{i}g(i)\\ g(n)&=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i)\\ \end{aligned} \]这里的关系矩阵\(A_{n,i}=(-1)^i\binom{n}{i}\)
可以使用代数证明，即证明\(A*A=I\)
也可以把上式移至下式（没错，其实是一样的
\[\begin{aligned} g(n)&=\sum_{i=0}^n(-1)^i\binom{n}{i}\sum_{j=0}^i(-1)^j\binom{i}{j}g(j)\\ &=\sum_{j=0}^n(-1)^jg(j)\sum_{i=j}^n\binom{n}{i}\binom{i}{j}(-1)^i\\ &=\sum_{j=0}^n(-1)^jg(j)\sum_{i=j}^n\frac{n!i!(n-j)!}{i!(n-i)!j!(i-j)!(n-j)!}(-1)^i\\ &=\sum_{j=0}^n(-1)^jg(j)\sum_{i=j}^n\binom{n}{j}\binom{n-j}{i-j}(-1)^i\\ &=\sum_{j=0}^n(-1)^j\binom{n}{j}g(j)\sum_{i=j}^n\binom{n-j}{i-j}(-1)^i\\ &=\sum_{j=0}^n(-1)^j\binom{n}{j}g(j)\sum_{i=0}^{n-j}\binom{n-j}{i}(-1)^{i+j}\\ &=\sum_{j=0}^n\binom{n}{j}g(j)(1-1)^{n-j}\\ &=\sum_{j=0}^n\binom{n}{j}g(j)[n-j=0]\\ &=g(n) \end{aligned} \]上面把组合数拆开，然后加入阶乘重新变形也是常用技巧
(2)贰之型
\[\begin{aligned} f(n)&=\sum_{i=0}^n\binom{n}{i}g(i)\\ g(n)&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)\\ \end{aligned} \]其实就是把\((-1)^i\)和\(g(i)\)合并了
这个也就是经典容斥（可以想想错排数）
(3)叁之型
\[\begin{aligned} f(n)&=\sum_{i=n}\binom{i}{n}g(i)\\ g(n)&=\sum_{i=n}(-1)^{i-n}\binom{i}{n}f(i) \end{aligned} \]我们转置上面贰之型的矩阵，就能得到了
这个柿子主要的意义在于它优美的组合意义（从这个角度你也可以组合意义证明）：
\(f(n)\)表示至少\(n\)个，\(g(n)\)表示恰好\(n\)个
(4)肆之型
\[\begin{aligned} f(n)&=\sum_{i=n}(-1)^i\binom{i}{n}g(i)\\ g(n)&=\sum_{i=n}(-1)^{i}\binom{i}{n}f(i) \end{aligned} \]同理移动了\((-1)^i\)
那么关于二项式反演的计算，展开来都可以观察到卷积形式，然后\(NTT\)加速
例：
【LOJ6503】Magic
有\(m\)种颜色，每种颜色有\(a_i\)个球（本质相同），一共\(n\)个球
求本质不同的\(n\)个球的排列数：满足相邻两个球颜色相同的位置恰好\(k\)个
对\(998244353\)取模
\(1\le n\le 10^5,1\le m\le2*10^4\)
样例
3 5 1
2 2 1
12
(AABCB ABBAC ABBCA...)
我们可以算出至少\(i\)个，然后再反演得到恰好\(k\)个
对应叁之型
于是枚举每个颜色形成多少个连续段
形成\(i\)个连续段的方案数是\(\binom{a-1}{i-1}\)，对应\(a-i\)个位置
于是写出生成函数（EGF）
\[\prod_{i=1}^m\sum_{j=1}^{a_i}\frac{\binom{a_i-1}{j-1}x^{j}}{j!} \]于是最终\([x^{i}]\)对应\(n-i\)个位置
我们有许多计算方式
1.直接分治\(NTT\)
每一层的总复杂度是\(O(n\log n)\)的，所以总复杂度就是\(O(n\log^2n)\)的
2.用堆维护，每次找出长度最小的两个合并
这个跟哈夫曼树很像，可以自行查阅，也是\(O(n\log^2 n)\)的复杂度
3.多维反演
事实上，任何几种反演关系都可以组合起来，得到多维反演
证明比较简单（用矩阵角度），不再阐述
错排数
与置换、环等问题有着紧密联系的数列
1.递推
对于\(n\)个数的排列\(p\)，\(\forall i\in[1,n],p_i\not =i\)的\(p\)的个数叫错排数
那么我们可以轻松得到递推关系
\[f_n=(n-1)(f_{n-1}+f_{n-2}) \]即要么跟一个错位的数换位置，要么跟一个在自己位置上的数换位置
2.生成函数形式
可以发现，错排就是大小\(\ge 2\)的置换的集合
于是我们可以得到其\(EGF\)
\[e^{-\ln(1-x)-x} \]3.环
对于给定的排列\(p\)，每次可以交换两个数，求把这个排列变为升序的最小交换次数
可以这样考虑：
一次交换即在一个置换环上拆一条边，拆散一个环即交换环长减一次
于是有
\[ans=\sum_{C}len(C)-1=n-S(C) \]\(S(C)\)即环的个数，注意自环也算
关于这一内容的题目，详见莫队去年出的【JZOJ7345】
卡特兰数
卡特兰数有多少种组合意义，你都知道吗？
1.生成函数形式
卡特兰数可以表示\(n\)个数的二叉树个数
于是有\(C(x)=1+C(x)xC(x)\)
即要么为空，要么由左儿子，根，右儿子组成
于是有
\[C(x)=\frac{1-\sqrt{1-4x}}{2x} \]2.通项
可以展开\(\sqrt{1-4x}\)
\[\begin{aligned} C(x)&=\frac{1-\sqrt{1-4x}}{2x}\\ &=\frac{1-\sum_{i=0}^{+\infty}\binom{\frac{1}{2}}{i}(-4x)^i}{2x} \end{aligned} \]于是有
\[\begin{aligned} C[n]&=-\frac{\binom{\frac{1}{2}}{n+1}(-4)^{n+1}}{2}\\ &=-\frac{(-4)^{n+1}\prod_{i=0}^n\frac{1-2i}{2}}{2(n+1)!}\\ &=-\frac{2^n\prod_{i=0}^n(2i-1)}{(n+1)!}\\ &=\frac{2^n\prod_{i=1}^n(2i-1)}{(n+1)!}\\ &=\frac{2^n(2n)!}{(n+1)!\prod_{i=1}^n2i}\\ &=\frac{\binom{2n}{n}}{n+1} \end{aligned} \]3.递推
(1)形式一
其实等价于二叉树的组合意义
\[C[0]=1,C[n]=\sum_{i=0}^{n-1}C[i]C[n-i-1] \](2)形式二
利用通项公式，有
\[\begin{aligned} C[n+1]&=\frac{\binom{2n+2}{n+1}}{n+2}\\ &=\frac{(2n+2)(2n+1)\binom{2n}{n}}{(n+1)^2(n+2)}\\ &=\frac{4n+2}{n+2}C[n] \end{aligned} \]4.格路计数
请出我们今天的主角
(1)格路计数壹之型
在平面直角坐标系上，一个点初始位置在原点
令其坐标为\((x,y)\)，每次可以走到\((x+1,y+1)\)或\((x+1,y-1)\)
问在\(y\in[0,+\infty]\)的情况下走到\((2n,0)\)的方案数
我们考虑折线法
假设没有限制，那么就是在\(2n\)步中选出\(n\)步向右上，即\(\binom{2n}{n}\)
考虑加入限制，将第一次跨过\(x\)轴的位置以后的路径沿\(y=-1\)翻折，这一部分就是要减去的答案，即\(\binom{2n}{n-1}\)
也就是\(C[n]=\binom{2n}{n}-\binom{2n}{n-1}\)
这里同时涉及了另一种组合意义：合法括号序列计数
(2)格路计数贰之型
在平面直角坐标系上，一个点初始位置在原点
令其坐标为\((x,y)\)，每次可以走到\((x+1,y+1)\)或\((x+1,y-1)\)
问在\(y\in [0,m]\)的情况下走到\((n,a)\)的方案数
同样考虑折线法
对于跨过\(x\)轴的，我们沿\(y=-1\)翻折，对于跨过\(y=m\)的，我们沿\(y=m+1\)翻折
但是可以发现，一条路径可能同时跨过这两条线，
于是我们交替翻折，容斥就能得到答案，这个过程也叫反射容斥
那么，如果是对于一整列所有的情况都要算的话就可以平衡规划做到\(O(n\sqrt n)\)
而若是单独求\((2n,0)\)，就可以变成单位根反演
\[\sum_{i=0}^{2n}([i\equiv n\ (mod\ m)]-[i\equiv n-1\ (mod\ m)])\binom{2n}{i} \]这个是由于翻折对\(m\)的余数的改变而整理出来的
(3)格路计数叁之型
在平面直角坐标系上，一个点初始位置在原点
令其坐标为\((x,y)\)，每次可以走到\((x+1,y+1)\)或\((x+1,y-1)\)或\((x+1,y)\)
问在\(y\in[0,m]\)的情况下走到\((n,0)\)的方案数，\(1\le n\le 10^7\)
由于容斥实际上在求无限制情况下走到一个点的方案数
那么我们把无限制情况下，走到最后一列所有位置的方案数求出来，然后再容斥就能算了
于是乎就变成了算\((x^{-1}+1+x)^n\)，\(ODE\)求解即可
实际上，上述几种形式本质上都是常系数其次线性递推，所以可以做更大的数据范围，这里就不展开了
斯特林数
这是极为重要的一类特殊计数序列，在涉及幂、集合、排列有关问题的推导时都有巨大用处
1.第一类斯特林数
设\(s(n,m)\)表示把\(n\)个互不相同的元素划分成互不区分的\(m\)个圆排列的方案数
有
\[s(n,m)=s(n-1,m-1)+(n-1)s(n-1,m) \](1)置换
\[\sum_{i=1}^ns(n,i)=n! \]\(n\)个数的置换恰好有\(n!\)个，于是证得
(2)一个排列问题
\(n\)个数的排列，其中前缀最大值的个数恰好为\(k\)的排列数为
\[s(n,k) \]可以这样分析：
我们先将数划分成\(k\)组，然后将它们按各组中的最大值排序
然后组内可以看成是钦定一个位置的排列（即最大值的位置），也就是环排列，故证得
(3)上升幂
\[x^{\overline n}=\sum_{i=0}^ns(n,i)x^i \]归纳证明：
当\(n=0\)时，显然成立
同时有
\[\begin{aligned} x^{\overline {n+1}}&=(x+n)\cdot x^{\overline n}\\ &=(x+n)\sum_{i=0}^ns(n,i)x^i\\ &=\sum_{i=0}^ns(n,i)x^{i+1}+\sum_{i=0}^nns(n,i)x^i\\ &=\sum_{i=1}^{n+1}s(n,i-1)x^i+\sum_{i=0}^nns(n,i)x^i\\ &=\sum_{i=0}^{n+1}s(n+1,i)x^i \end{aligned} \](4)下降幂
\[x^{\underline n}=\sum_{i=0}^n(-1)^{n-i}s(n,i)x^i \]结合上一条结论，运用\(x^{\underline n}=(-1)^n(-x)^{\overline n}\)即可
2.第二类斯特林数
设\(S(n,m)\)表示把\(n\)个互不相同的元素划分成互不区分的\(m\)个集合的方案数
有
\[S(n,m)=S(n-1,m-1)+mS(n-1,m) \](1)通项公式
\[S(n,m)=\sum_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!} \]考虑容斥
如果没有集合非空的限制，可以认为是\(m^n\)
那么我们枚举空集合的数量，最后因为集合互不区分，再除掉一个\(m!\)即可
(2)普通幂
\[x^n=\sum_{i=0}^nS(n,i)x^{\underline i} \]可以组合意义
给\(n\)个有标号小球用\(x\)种颜色染色，就是\(x^n\)
可以考虑先将小球分成\(i\)个集合，然后每个集合染一种颜色，即\(S(n,i)\binom{x}{i}i!\)
由于第二类斯特林数中集合不区分，再乘回一个\(i!\)
3.斯特林数的四种求法
(1)行·第一类斯特林数
观察
\[x^{\overline n}=\sum_{i=0}^ns(n,i)x^i \]那么要求的就是\(x^{\overline n}\)
考虑到\(x^{\overline {2n}}=(x+n)^{\overline n}x^{\overline n}\)
可以倍增\(FFT\)
(2)列·第一类斯特林数
考虑它的\(EGF\)
一个环为\(-\ln(1-x)\)
那么\(n\)个环为
\[\frac{(-\ln(1-x))^n}{n!} \](3)行·第二类斯特林数
可以用通项公式
\[\sum_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!} \]观察到这是卷积形式，于是直接做完了
(4)列·第二类斯特林数
同样考虑\(EGF\)
一个非空集合是\(e^x-1\)
那么\(n\)个集合就是
\[\frac{(e^x-1)^n}{n!} \]4.斯特林反演
基本柿子
\[f[n]=\sum_{i=0}^nS(n,i)g[i]\iff g[n]=\sum_{i=0}^ns(n,i)(-1)^{n-i}f[i] \]证明如下：
令\(F(x)\)为\(f\)的\(EGF\)，\(G(x)\)为\(g\)的\(EGF\)
\[\begin{aligned} F(x)&=\sum_{i=0}^{+\infty}\frac{f[i]x^i}{i!}\\ &=\sum_{i=0}^{+\infty}\frac{x^i}{i!}\sum_{j=0}^iS(i,j)g[j]\\ &=\sum_{j=0}^{+\infty}g[j]\sum_{i=0}^{+\infty}\frac{x^iS(i,j)}{i!}\\ &=\sum_{j=0}^{+\infty}\frac{g[j](e^{x}-1)^j}{j!}\\ &=G(e^x-1)\\ G(x)&=F(\ln(1+x))\\ &=\sum_{i=0}^{+\infty}\frac{f[i](\ln(1+x))^i}{i!}\\ &=\sum_{i=0}^{+\infty}f[i](-1)^i\sum_{j=0}^{+\infty}\frac{s(j,i)(-x)^j}{j!}\\ &=\sum_{j=0}^{+\infty}\frac{x^j}{j!}\sum_{i=0}^jS(j,i)(-1)^{j-i}f[i] \end{aligned} \]第四步和倒数第二步运用了一列的\(EGF\)
其它形式可以类比二项式反演得到
那么幂的转换我们也可以用这种方式轻松得到了
例1：
【清华集训2016】如何优雅地求和
典中典，不讲了，建议推一推线性做法锻炼一下
例2：
【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\)取模。
\(1\le n,k\le 2*10^5\)
首先可以发现 ，答案一定有个\(\sum w_i\)做因子，可以通过思考每个数单独的贡献得出，即每个数在拆分面前地位相同
于是答案可写成\(c\sum w_i\)
于是我们转化成求\(c\)，也就是每个数贡献的常数
(1)Sol1
\[c=\sum_{i=1}^ni\binom{n-1}{i-1}S(n-i,k-1) \]然后可以\(MTT\)，不必多说
(2)Sol2
大力推上面的柿子直到不需要\(MTT\)为止，留作练习
(3)Sol3
考虑组合意义
对于一个数来说，贡献的系数相当于它和所在集合里所有的数配对，每次配对一个就\(+1\)
那么第一种情况是和自己配对，在所有的情况下都成立，即\(S(n,k)\)
第二种是和别的数配对，即\((n-1)S(n-1,k)\)，于是用通项公式计算斯特林数就可以了
伯努利数
一个简洁有力的处理自然数幂和的工具
1.基本形式
这里用的是cmd给出的非经典伯努利数
不过笔者在使用中发现这样更简洁，所以借此安利一下
我们考虑自然数幂和的\(EGF\)
即
\[\begin{aligned} \sum_{i=0}^{n-1}i^k&=k![x^{k}]\sum_{i=0}^{n-1}e^{ix}\\ &=k![x^{k}]\frac{e^{nx}-1}{e^{x}-1}\\ &=k![x^{k}]\frac{e^{nx}-1}{x}\frac{x}{e^{x}-1} \end{aligned} \]最后面的部分\(\frac{x}{e^{x}-1}\)就是伯努利数，因为求逆的需要，我们才给了一个\(x\)上去
于是用这个卷积形式推下去
\[\begin{aligned} \sum_{i=0}^{n-1}i^k&=k!\sum_{i=0}^{k}\frac{n^{i+1}B_{k-i}}{(i+1)!} \end{aligned} \]可以发现，在多个\(k\)的情况下，伯努利数可以在一次卷积内完成计算
2.递推
我们令\(n=1\)，\(k>0\)，特别地，\(B_0=1\)
于是有
\[\begin{aligned} 0&=\sum_{i=0}^k\frac{B_{k-i}}{(i+1)!}\\ B_k&=-\sum_{i=0}^{k-1}\frac{B_{i}}{(k-i+1)!} \end{aligned} \]分拆数
由于出现还算频繁，所以也是很重要的一类计数序列呢
1.生成函数
我们定义一个数的拆分数为，将这个数用正整数拆分的不同集合的个数
即：\(1+2+3\)和\(1+3+2\)视为同一种
你也可以理解为\(MSET(\N^+)\)
那么枚举每个数选多少次，可以得到
\[\prod_{i=1}\frac{1}{1-x^i} \]2.爆算
即先取\(\ln\)再\(\exp\)
比较通用，缺点是模数不是\(NTT\)模数时会比较痛苦
3.五边形数定理
我们可以利用五边形数定理
这个定理由欧拉给出：
\[\prod_{i=1}(1-x^i)=1+\sum_{i=1}(-1)^ix^{\frac{i(3i\pm1)}{2}} \]具体的证明有些复杂，可以自行查阅
这里给出一个参考：五边形数定理的一种证明
有了这个定理，就可以发现有用的项只有\(O(\sqrt{n})\)个，于是我们可以\(O(n\sqrt{n})\)暴力求逆计算
4.Ferrers图
如\(10=1+3+6\)
其对应的\(Ferrers\)图为
\(■\) \(■\) \(■\) \(■\) \(■\) \(■\)
\(■\) \(■\) \(■\)
\(■\)
即从大到小排列
有了这个图我们可以做很多问题
(1)限制拆分个数
我们将一个\(Ferrers\)图翻转，可以得到另一个\(Ferrers\)图
如上图变为
\(■\) \(■\) \(■\)
\(■\) \(■\)
\(■\) \(■\)
\(■\)
\(■\)
\(■\)
记\(F_{n,m}\)为将\(n\)拆分为不超过\(m\)个数的方案数
那么\(F_{n,m}\)就等价于用大小不超过\(m\)的数进行拆分
例：
【P5824】十二重计数法
留作练习
(2)每个数至多选一个
给出一个\(Ferrers\)图（这里是竖着放的）
\(■\) \(■\) \(■\) \(■\) \(■\) \(■\)
\(■\) \(■\) \(■\) \(■\) \(■\)
\(■\) \(■\) \(■\) \(■\)
\(■\) \(■\) \(■\) \(■\)
\(■\) \(■\) \(■\)
\(■\) \(■\)
\(■\)
\(■\)
我们找到最大的\(45°\)三角，设长度为\(h\)（这里就为\(6\)）
删掉之后就会变成
\(■\) \(■\) \(■\) \(■\)
\(■\)
于是就变成了（横着看）大小不超过\(h\)的\(Ferrers\)图
于是有
\[\prod_{i=1}^n(1+x^i)=\sum_{h=1}^{+\infty}x^{\frac{h(h+1)}{2}}\prod_{i=1}^h\frac{1}{1-x^i} \]我们还可以对此扩展
\[\prod_{i=k+1}^n(1+x^i)=\sum_{h=1}^{+\infty}x^{kh}\cdot x^{\frac{h(h+1)}{2}}\prod_{i=1}^h\frac{1}{1-x^i} \](3)分拆数的第三种计算方式
结合以上两种我们可以得到EI给出的第三种计算方式
\(■\) \(■\) \(■\) \(■\) \(■\) \(■\)
\(■\) \(■\) \(■\) \(■\) \(■\)
\(■\) \(■\) \(■\) \(■\)
\(■\) \(■\) \(■\) \(■\)
\(■\) \(■\) \(■\)
\(■\) \(■\)
\(■\)
\(■\)
还是这个图
我们从原点引\(y=-x\)的直线
可以得到一个正方形，设大小为\(h\)（这里就是\(4\)）
删去正方形后，由翻转的性质，剩下的就是两个大小不超过\(h\)的整数拆分
于是
\[\prod_{i=1}\frac{1}{1-x^i}=\sum_{h\ge 1}x^{h^2}(\prod_{i=1}^h\frac{1}{1-x^i})^2 \]由于\(h\le \sqrt{n}\)，所以我们可以快速计算
分治与倍增
分治ntt实际是一种思想，基本上就是正常的分治上用ntt维护转移之类的
同样的，倍增ntt也是一样的思想，一般我们的目标能够使用一个多项式的前\(n\)快速计算出\(n+1\sim 2n\)项，所以重点还是在公式的推导
1.分治NTT
给出一个序列\(g_{1...n-1}\)，求出\(f_{0...n-1}\)，其中\(f_i=\sum_{j=1}^if_{i-j}g_j\)。
初始时有\(f_0=1\)，对\(998244353\)取模
考虑分治求解\(f\)的过程
不妨假设我们目前要求的是\(l\sim r\)间的\(f\)，且$l\sim mid \(之间的\)f$已经求完了
那么我们可以求出\(l\sim mid\)的\(f\)对\(mid+1\sim r\)的贡献
具体的，有\(w_x=\sum_{i=l}^{mid}f_ig_{x-i}\)，其中\(x\)有效的范围是\(mid+1\sim r\)，可以发现这样我们贡献的来源和要求的东西之间是没有影响的，每次直接\(NTT\)一下就可以了
然后可以继续分治下去做\(mid+1\sim r\)
时间复杂度\(T(n)=2T(\frac n 2)+O(n\log n)=O(n\log^2n)\)
2.倍增NTT
求\(x^{\overline n }\)
不妨考虑倍增：假设我们现在有\(x^{\overline n}\)，要求\(x^{\overline{2n}}\)，问题变为如何用\(x^{\overline n}\)快速求出\((x+n)^{\overline n}\)
不妨设其为\(f(x)\)，设\(f_i=[x^i]f(x)\)，那么
\[\begin{aligned} f(x+k)&=\sum_{i=0}^nf_i(x+k)^i\\ &=\sum_{i=0}f_i\sum_{j=0}^i\binom{i}{j}x^jk^{i-j}\\ &=\sum_{j=0}^nx^j\sum_{i=j}^nf_i\frac{i!}{j!(i-j)!}k^{i-j}\\ &=\sum_{j=0}^n\frac{x^j}{j!}\sum_{i=j}^nf_i\frac{i!}{(i-j)!}k^{i-j}\\ \end{aligned} \]然后我们就得到了\(f(x+k)\)的式子，最后把\(f(x)\)与\(f(x+k)\)卷一下就好了
时间复杂度\(T(n)=T(\frac n 2)+O(n\log n)=O(n\log n)\)
分式分解
由于笔者碰到的分式分解题比较少，所以这里只对最基础的分式分解讲解
其扩展有兴趣可以查阅资料
1.单个二次式的分式分解
一个经典的例子是斐波拉契数列
\[\begin{aligned} [x^n]\frac{x}{1-x-x^2}&=[x^{n-1}](\frac{A}{x-a}+\frac{B}{x-b})\\ &=A[x^{n-1}]\frac{1}{x-a}+B[x^{n-1}]\frac{1}{x-b}\\ &=-Aa^{-n}-Bb^{-n}\\ &=\frac{\sqrt 5}{5}[(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n] \end{aligned} \]其中的\(A,B,a,b\)都可以通过列方程解出
来看道运用
例：
【CF755G】PolandBall and Many Other Balls
有一排\(n\)个球，定义一组可以只包含一个球或包含两个相邻的球。现在每个球只能分到一个组里面，求从这些球中选出\([1,k]\)组的方案数对\(998244353\)取模的结果
\(1\le n\le 10^9,1\le k\le 2^{15}\)
样例
3 3
5 5 1
设前\(n\)个球分组的生成函数为\(F_n(x)\)
则有
\[F_n(x)=(1+x)F_{n-1}(x)+xF_{n-2}(x) \]设\(G(x,y)\)表示\(\sum_{i=0}^{+\infty}y^iF_i(x)\)
\[\begin{aligned} (1+x)yG+xy^2G+1&=G\\ G&=\frac{1}{1-y-xy-xy^2}\\ \end{aligned} \]当然用\(SEQ\)构造可以更快得到
然后套用上面的做法
虽然解出的根是根式，但是发现它是一个\(\sqrt{1+6x+x^2}\)，可以通过\(ODE\)线性计算，也可以多项式开根
2.多个不同一次式的分式分解
形如
\[\frac{P(x)}{\prod_{i=1}^n(a_ix+b_i)}=\sum_{i=1}^n\frac{K_i}{a_ix+b_i} \]将两边同时乘上\(\prod_{i=1}^n(a_ix+b_i)\)
有
\[P(x)=\sum_{i=1}^nK_i\prod_{j\not =i}(a_jx+b_j) \]代入\(-\frac{b_i}{a_i}\)（这也就是为什么要求因式不同）
\[P(-\frac{b_i}{a_i})=K_i\prod_{j\not =i}(-\frac{a_jb_i}{a_i}+b_j) \]令\(A(x)=\prod_{i=1}^n(a_ix+b_i)\)，则
\[\begin{aligned} K_i&=\lim_{x\to -\frac{b_i}{a_i}}\frac{P(x)(a_ix+b_i)}{A(x)}\\ &=\frac{P(-\frac{b_i}{a_i})a_i}{A'(-\frac{b_i}{a_i})} \end{aligned} \]这一步运用了洛必达法则
于是我们可以多点求值在\(O(n\log^2n)\)内完成
例：
【JZOJ7567】傅里叶与矩阵
属于基础运用，就不讲了
3.重一次式的分式分解
形如
\[\frac{P(x)}{(ax+b)^n}=\sum_{i=1}^n\frac{K_i}{(ax+b)^i} \]将\((ax+b)^n\)乘过去
有
\[P(x)=\sum_{i=1}^nK_i(ax+b)^{n-i} \]只需对两边都求\(n-1,n-2,n-3\cdots 1\)阶导，对比系数，然后一个个算出来
积和变换
对于多个形式类似的式子的和或积，我们可以运用对数，导数等相关性质使得其能在二者间转换
这类问题往往靠经验积累，所以我们多以实际题目讲解
1.和化积
例：
【P4705】玩游戏
对于一次游戏，给出长为\(n\)的序列\(a\)，长为\(m\)的序列\(b\)。从两个序列里随机取出一个数，分别设为\(a_x\), \(b_y\)
定义这次游戏的\(k\)价值为 \((a_x + b_y)^k\)
计算对于\(k=1,2,\cdots,t\)，游戏价值的期望模\(998244353\)的结果
\(1\le n,m,t\le 10^5,0\le a_i,b_i<998244353\)
容易写出答案
\[\begin{aligned} \frac{1}{nm}\sum_{i=1}^n\sum_{j=1}^m(a_i+b_j)^k&=\frac{1}{nm}\sum_{p=0}^k\sum_{i=1}^n\sum_{j=1}^m\binom{k}{p}a_i^pb_j^{k-p}\\ &=\frac{k!}{nm}\sum_{p=0}^k\sum_{i=1}^n\sum_{j=1}^m\frac{a_i^pb_j^{k-p}}{p!(k-p)!} \end{aligned} \]设\(A(x)=\sum_{i=0}^{+\infty}\frac{x^i}{i!}\sum_{j=1}^na_j^i,B(x)=\sum_{i=0}^{+\infty}\frac{x^i}{i!}\sum_{j=1}^nb_j^i\)
于是要算的就是二者的卷积
我们先把阶乘去掉，最后再乘回来
\[\begin{aligned} A(x)&=\sum_{i=0}^{+\infty}x^i\sum_{j=1}^na_j^i\\ &=\sum_{j=1}^n\sum_{i=0}^{+\infty}a_j^ix^i\\ &=\sum_{j=1}^n\frac{1}{1-a_jx} \end{aligned} \]这个时候已经可以分治\(NTT\)计算了，但是常数巨大，考虑优化
观察：
\[[\ln(1-a_jx)]'=\frac{-a_j}{1-a_jx},[f(x)+g(x)]'=f'(x)+g'(x) \]于是可以改写上面的柿子
\[\begin{aligned} A(x)&=-x\sum_{j=1}^n[\ln(1-a_jx)]'+n\\ &=-x[\ln{(\prod_{i=1}^n(1-a_ix))}]'+n \end{aligned} \]2.积化和
例1：
【P5850】calc加强版
对于\(n=1,2,3 ... m\)，求出所有合法序列的权值对\(998244353\)取模的结果
其中，合法的定义为每个元素都为\([1,k]\)中的整数，同时每个元素都不相同，同时，权值为所有元素的乘积
两个序列不同当且仅当他们任意一位不一样
\(1\le m\le 5*10^5\)，\(1\le k\le998244353\)
不难发现，对于一个\(n\)
答案就是
\[n![x^n]\prod_{i=1}^k(1+ix) \]先取对数后\(exp\)
\[\begin{aligned} n![x^n]\prod_{i=1}^k(1+ix)&=n![x^n]\exp(\sum_{i=1}^k\ln(1+ix))\\ &=n![x^n]\exp(\sum_{i=1}^k-\sum_{j=1}^{+\infty}\frac{(-ix)^j}{j})\\ &=n![x^n]\exp(-\sum_{j=1}^{+\infty}\frac{(-1)^jx^{j}}{j}\sum_{i=1}^ki^j) \end{aligned} \]自然数幂和可以伯努利数求解
例2：
【JZOJ7514】萌萌计数题
对于所有长度为\(n\)的排列，求逆序对数量的\(k\)次方的期望对\(998244353\)取模的结果
\(1\le n\le 998244350,1\le k\le 10^5\)
如果\(k=1\)
将数字从小到大插入序列，可以写出生成函数
\[\prod_{i=0}^{n-1}\frac{1-x^{i+1}}{1-x} \]加入\(k\)次方，实际上是一个类似这样的过程
有\(n\)个数\(a_1...a_n\)，即值为\(i\)的产生的逆序对个数
求\((\sum_{i=1}^na_i)^k\)
对其使用多元二项式定理
即\(\sum_{b_1+...b_n=k}\binom{k}{b_1...b_n}\prod_{i=1}^na_i^{b_i}\)
于是我们可以把上式的\(x\)改写为\(e^x\)
\[\begin{aligned} \frac{k!}{n!}[x^k]\prod_{i=0}^{n-1}\frac{1-e^{(i+1)x}}{1-e^x}&=\frac{k!}{n!}[x^k](\frac{x}{e^x-1})^n\prod_{i=1}^n\frac{e^{ix}-1}{x}\\ &=k^n\prod_{i=1}^n\frac{e^{ix}-1}{ix} \end{aligned} \]观察右边的乘积，是一个复合的形式
于是设\(F(x)=\ln \frac{e^x-1}{x}\)
于是柿子变为
\[\begin{aligned} k![x^k]\exp{(\sum_{i=1}^nF(ix)-nF(x))}&=k![x^k]\exp{(\sum_{i=1}^n\sum_{j=1}^{+\infty}f_j(ix)^j-nF(x))}\\ &=k![x^k]\exp{(\sum_{j=1}^{+\infty}f_jx^j\sum_{i=1}^ni^j-nF(x))} \end{aligned} \]同样可以伯努利数求解
牛顿级数与下降幂多项式
这是两类在推导组合数有关柿子时十分有用的多项式
1.下降幂多项式
对于一个多项式\(F(x)=\sum_{i=0}^nf_ix^i\)
其下降幂多项式定义为\(G(x)=\sum_{i=0}^ng_ix^{\underline i}\)
考虑怎么求
(1)点值转下降幂多项式
若给出了\(n+1\)个连续点值
令其为\(a\)，即\(a_i=F(i)\)
那么有
\[\begin{aligned} a_i&=\sum_{j=0}^ng_ji^{\underline j}\\ &=\sum_{j=0}^ng_j\frac{i!}{(i-j)!}\\ \frac{a_i}{i!}&=\sum_{j=0}^n\frac{g_j}{(i-j)!} \end{aligned} \]令\(a\)的\(EGF\)为\(A(x)\)
于是有\(A(x)=G(x)e^{x}\)，即\(G(x)=A(x)e^{-x}\)
(2)普通多项式转下降幂多项式
如果允许\(O(n^2)\)
则
\[\begin{aligned} \sum_{i=0}^nf_ix^i&=\sum_{i=0}^nf_i\sum_{j=0}^ix^{\underline j}S(i,j)\\ &=\sum_{j=0}^nx^{\underline j}\sum_{i=j}^nS(i,j)f_i \end{aligned} \]如果不允许，则可以先多点求值求出连续点值，然后再卷积
(3)下降幂多项式转普通多项式
可以直接乘上一个\(e^x\)转成点值的\(EGF\)，然后再快速插值
2.牛顿级数
对于一个多项式\(F(x)=\sum_{i=0}^nf_ix^i\)
其牛顿级数定义为\(G(x)=\sum_{i=0}^ng_i\binom{x}{i}\)
那么它跟下降幂多项式有着非常明显的关系，只要乘除\(i!\)就能在二者间进行转换
拉格朗日反演
在用各种变形得到最后的生成函数时，我们可能会因为其诡异的形式而不知如何计算
而拉格朗日反演在复合逆可以快速求解的情况下给了我们一条捷径
1.复合逆
对于两个多项式\(F(x),G(x)\)
若\(F(G(x))=x\)，则\(F,G\)互为复合逆
由定义可知\(F,G\)没有常数项且一次项非\(0\)（一般是\(1\)）
所以在求解复合逆的时候，若原函数无复合逆，要对其进行变换，如求逆，次方等
2.拉格朗日反演
对于互为复合逆的\(F,G\)
有
\[[x^n]G(x)=\frac{1}{n}[x^{-1}]F(x)^{-n} \]或者说为了计算，有
\[[x^n]G(x)=\frac{1}{n}[x^{n-1}](\frac{F(x)}{x})^{-n} \]- \(Claim:\)
对于常系数为\(0\)，且一次项非\(0\)的整式（即不存在负指数幂项）\(F(x)\)
有
\[[x^{-1}]F'F^k=[k=-1] \]证明：
当\(k\not =-1\)，\(F'F^k=(\frac{1}{k+1}F^{k+1})'\)，由于多项式求导之后没有\(-1\)次项，故这时为\(0\)
当\(k=-1\)，\([x^{-1}]F'F^{-1}=[x^{-1}]\frac{F(x)'}{F(x)}=[x^{0}]\frac{F(x)'}{x^{-1}F(x)}=1\)
于是对于拉格朗日反演：
\[\begin{aligned} G(F(x))&=x\\ G'(F)F'&=1\\ \sum_{i=0}^{+\infty}iG[i]F^{i-1}F'&=1\\ \sum_{i=0}^{+\infty}iG[i]F^{i-n-1}F'&=F^{-n}\\ [x^{-1}]\sum_{i=0}^{+\infty}iG[i]F^{i-n-1}F'&=[x^{-1}]F^{-n}\\ \sum_{i=0}^{+\infty}iG[i][i-n-1=-1]&=[x^{-1}]F^{-n}\\ nG[n]&=[x^{-1}]F^{-n}\\ G[n]&=\frac{1}{n}[x^{-1}]F^{-n} \end{aligned} \]类似地我们还能得到
\[G^k[n]=\frac{k}{n}[x^{-k}]F^{-n} \]3.扩展拉格朗日反演
对于互为复合逆的\(F,G\)，以及另一个无要求的\(H\)
令\(T(x)=H(G(x))\)
有
\[T[n]=\frac{1}{n}[x^{-1}]H'F^{-n} \]证明：
\[\begin{aligned} H(G(F(x)))&=H(x)\\ T(F)&=H\\ T'(F)F'&=H'\\ \sum_{i=0}^{+\infty}iT[i]F^{i-1}F'&=H'\\ [x^{-1}]\sum_{i=0}^{+\infty}iT[i]F^{i-1-n}F'&=[x^{-1}]H'F^{-n}\\ \sum_{i=0}^{+\infty}iT[i][i-n-1=-1]&=[x^{-1}]H'F^{-n}\\ nT[n]&=[x^{-1}]H'F^{-n}\\ T[n]&=\frac{1}{n}[x^{-1}]H'F^{-n} \end{aligned} \]例：
【P7439】「KrOI2021」Feux Follets 弱化版
设\(cyc_\pi\)表示将长度为\(n\)的排列\(\pi\)当成置换时能分解的循环置换个数。给定\(n,k\)和一个\(k-1\)次多项式\(F(x)\)
求\(\sum_{\pi}F(cyc_{\pi})\)对\(998244353\)取模的结果，其中\(\pi\)是长度为\(n\)的错排列
\(1\le n,k\le 10^5\)
一个长度\(\ge 2\)的环的\(EGF\)是\(G(x)=\sum_{i\ge2}\frac{x^i}{i}=-\ln(1-x)-x\)
那么要求的就是\(\sum_{i=1}^{+\infty}\frac{G^i(x)}{i!}[x^n]n!F(i)\)
设\(P_k(x)=G^k(x)\)
于是可以施扩展拉格朗日反演
但是我们发现\(G\)的最低次数是\(2\)，而且系数为\(2^{-1}\)，不满足复合逆的要求
不妨设\(\frac{g^2}{2}=-\ln(1-x)-x\)，那么复合逆存在，设为\(f\)
那么柿子改写成
\[\begin{aligned} [x^n]P_k(x)&=\frac{g^{2k}}{2^k}\\ &=\frac{1}{n}[x^{-1}]\frac{2k\cdot x^{2k-1}}{2^k}f^{-n}\\ &=\frac{1}{n}[x^{n-2k}]\frac{1}{2^{k-1}}(\frac{f}{x})^{-n} \end{aligned} \]牛顿迭代求出来然后多点求值即可
关于幂次上的应用，还有一些扩展：
【P7857】「EZEC-9」Meltel（by Alpha1022）
4.另类拉格朗日反演
当\(k\not =0\)时，有
\[\begin{aligned} G^k[n]&=\frac{k}{n}[x^{-k}]F^{-n}\\ &=\frac{k}{n}\frac{1}{-k}[x^{-k-1}](-n)F^{-n-1}F'\\ &=[x^{-k-1}]F^{-n-1}F' \end{aligned} \]在\(n=0\)时有奇效
例：
【P7445】「EZEC-7」线段树
给出一个长\(n\)的序列，对其建出一颗线段树
有\(m\)次操作，每次在序列的所有子区间中等概率选出一个，然后在\([-1,V]\)中等概率选出一个整数\(C\)
对选出的区间在线段树上执行区间加上\(C\)的操作
线段树有懒标记，但是是在所有操作做完之后一起下传
若线段树上一个非叶子节点的\(tag\)不为\(0\)，就会\(pushdown\)，求期望的\(pushdown\)次数
对\(998244353\)取模
\(1\le n\le 10^5,1\le m\le 10^5\)
样例
2 1 0
166374059(1/6)
我们对一个点进行考虑
计算它最终为\(0\)的概率，再用\(1\)减去，然后求和就是答案
我们不需要考虑操作具体到了哪些点上，因为只要是其子区间就会被下传到
设\(p(a)\)表示线段树上一个点对应区间\([l,r]\)在一次操作中被覆盖到的概率，即\(\frac{l(n-r+1)}{\frac{n(n+1)}{2}}\)
于是可以写出为\(0\)的概率
\[\sum_{i=0}^{m}\binom{m}{i}p(a)^i(1-p(a))^{m-i}[x^0](\frac{\frac{x^{V+1}-1}{x-1}+x^{-1}}{V+2})^i \]注意到我们最后是求和的，于是我们可以考虑先计算出中间部分\(p(a)^i(1-p(a))^{m-i}\)对于所有\(i\)的和
由于\(p(a)^i(1-p(a))^{m-i}=(1-p(a))^m(\frac{p(a)}{1-p(a)})^i\)
所以可以写成生成函数加和的形式，分治\(NTT\)计算
然后考虑算后面部分
设\(F(x)=\frac{x^{V+1}-1}{x-1}+x^{-1}\)
于是要对于\(\forall i\in[0,m]\)，计算\([x^0]F^i(x)\)
这时候可以使用另类拉格朗日反演了
但是我们注意到\(F\)显然没有复合逆，但是\(F^{-1}\)有
于是设\(G(x)=F^{-1},G(P(x))=x\)
那么\([x^0]F^i(x)=[x^0]G^{-i}(x)=[x^{i-1}]P'P^{-1}\)
把\(P\)代入\(G\)有
\[\begin{aligned} x&=G(P(x))\\ x&=\frac{1}{\frac{P^{V+1}-1}{P-1}+P^{-1}}\\ x&=\frac{P^2-P}{P^{V+2}-1}\\ xP^{V+2}-x&=P^2-P\\ xP^{V+2}-P^2+P-x&=0 \end{aligned} \]牛顿迭代求解即可
ODE
\(ODE\)，即常微分方程，也就是万能的求导大法，可以帮助解决一类线性递推有关的题目
这里介绍的只是\(ODE\)的冰山一角，更多的姿势可以在具体的题目中学习
1.幂
(1)壹之型
最经典的\(ODE\)
\[\begin{aligned} G(x)&=F(x)^k\\ G'&=kF^{k-1}F'\\ FG'&=kGF' \end{aligned} \]那么在\(F\)是特殊多项式（如短多项式）时，可以快速得到递推形式
(2)贰之型
\[\begin{aligned} G(x)&=(x+1)^n(x-1)^m\\ G'(x)&=\frac{nG}{x+1}+\frac{mG}{x-1}\\ (x^2-1)G'(x)&=n(x-1)G+m(x+1)G \end{aligned} \]当然，这里不是\((x+1),(x-1)\)时也是类似的
2.阶乘
\[\begin{aligned} G(x)&=\sum_{i=0}^{+\infty}i!x^i\\ G'(x)&=\sum_{i=0}^{+\infty}(i+1)!(i+1)x^{i}\\ x^2G'(x)&=\sum_{i=2}^{+\infty}(i-1)!(i-1)x^{i}\\ &=\sum_{i=2}^{+\infty}i!x^i-\sum_{i=2}^{+\infty}(i-1)!x^i\\ &=\sum_{i=0}^{+\infty}i!x^i-x\sum_{i=0}^{+\infty}i!x^i-x-1+x\\ &=(1-x)G(x)-1\\ \end{aligned} \]可以做一些复合问题
3.二项式
(1)原初之型
\[\begin{aligned} G(x)&=\sum_{i=0}^k\binom{n}{i}x^i\\ G'(x)&=\sum_{i=0}^{k-1}\binom{n}{i+1}(i+1)x^{i}\\ nG(x)-(1+x)G'(x)&=\sum_{i=0}^{k}\binom{n}{i}(n-i)x^i-\sum_{i=0}^{k-1}\binom{n}{i+1}(i+1)x^{i}\\ &=\binom{n}{k}(n-k)x^k \end{aligned} \](2)扩展
\[\begin{aligned} T(x)&=\sum_{i=0}^k\binom{n}{i}A^i\\ G(x)&=\sum_{i=0}^k\binom{n}{i}x^i\\ T(x)&=G(A)\\ T'(x)&=G'(A)A'\\ nG(A)-(1+A)G'(A)&=\binom{n}{k}(n-k)A^k\\ nA'T(x)-(1+A)T'(x)&=\binom{n}{k}(n-k)A^kA' \end{aligned} \](3)再扩展
\[\begin{aligned} G(x)&=\sum_{i=0}^k\binom{n}{i}A^iB^{n-i}\\ &=B^n\sum_{i=0}^k\binom{n}{i}(\frac{A}{B})^i\\ T(x)&=\sum_{i=0}^k\binom{n}{i}(\frac{A}{B})^i\\ n(\frac{A}{B})'T-(1+\frac{A}{B})T'&=\binom{n}{k}(n-k)(\frac{A}{B})^k(\frac{A}{B})'\\ \end{aligned} \]\[G=TB^n,G'B=T'B^{n+1}+nGB'\\ \]于是可以表示出\(T,T'\)
\[\begin{aligned} n(\frac{A}{B})'\frac{G}{B^n}-(1+\frac{A}{B})\frac{G'B-nGB'}{B^{n+1}}&=\binom{n}{k}(n-k)(\frac{A}{B})^k(\frac{A}{B})'\\ \frac{n(A'B-AB')G-G'B^2+nGB'B-G'BA+nGB'A}{B^{n+2}}&=\binom{n}{k}(n-k)\frac{A^k}{B^k}\frac{A'B-AB'}{B^2}\\ n(A'B-AB')G-G'B^2+nGB'B-G'BA+nGB'A&=\binom{n}{k}(n-k)A^kB^{n-k}(A'B-AB')\\ n(A'B+B'B)G-(B^2+BA)G'&=\binom{n}{k}(n-k)A^kB^{n-k}(A'B-AB')\\ n(A'+B')G-(A+B)G'&=\binom{n}{k}(n-k)(A'B^{n-k}A^k-A^{k+1}B'B^{n-k-1})\\ \end{aligned} \]同样可以做一些复合问题
关于\(ODE\)的一个应用：Binomial Sum（见EI博客）
转置原理
处理生成函数的重要技巧
1.定理
设有一个矩阵\(V\)，将其分解为几个初等矩阵\(E_1\cdots E_k\)
即
\[V=E_1E_2\cdots E_k \]则
\[V^{T}=E_k^TE_{k-1}^T\cdots E_1^T \]矩阵的转置：\(V^{T}_{j,i}=V_{i,j}\)，即沿对角线翻折
其中，初等矩阵分为三种：
(1)将\(I\)的第\(i\)行，第\(j\)行交换的矩阵
(2)将\(I_{i,i}\)从\(1\)改为\(c\)的矩阵
(3)将\(I_{i,j}\)从\(0\)改为\(c\)的矩阵
（\(I\)为单位矩阵）
左乘向量的效果分别为：
(1)交换第\(i,j\)位
(2)将第\(i\)位乘上\(c\)
(3)将第\(j\)位乘\(c\)，然后加到第\(i\)位上
对应的转置的效果：
(1)、(2)跟原来一样
(3)将第\(i\)位乘\(c\)，然后加到第\(j\)位上
手画一下应该很好理解
于是转置原理的用处就可以发现了：
在原变换不易计算时，可以计算转置，然后将整个过程倒过来再算
2.多点求值
这是一个经典的科技应用
规避了多项式取模，获得常数极小的做法
在\(rqy\)的博客里有非常详细的介绍
3.计算多元函数
对于一个多元函数\(F(x,y)\)
如果我们要求\([y^n]\)，我们可以将\(F\)转置，于是变成了求\([x^n]\)
于是只要我们知道求\([x^n]F(x,y)\)的方法，将其转置过来就是原问题的答案
例：
【P7440】「KrOI2021」Feux Follets
设\(cyc_\pi\)表示将长度为\(n\)的排列\(\pi\)当成置换时能分解的循环置换个数。给定\(n,k\)和一个\(k-1\)次多项式\(F(x)\)
对于\(\forall m\in[1,n]\)
求\(\sum_{\pi}F(cyc_{\pi})\)对\(998244353\)取模的结果，其中\(\pi\)是长度为\(n\)的错排列
\(1\le n,k\le 10^5\)
这个问题要求我们算每一项，所以原先的拉格朗日反演不管用了
考虑改成较为简洁的形式
\[G(x)=-\ln(1-x)-x\\ \sum_{i=0}^{+\infty}\frac{G^i(x)}{i!}\sum_{j=0}^{i-1}f_ji^j \]注意到右边有\(i^j\)不好处理
于是可以将\(F(x)\)改写成牛顿级数\(\sum_{i=0}^{k-1}f^*_j\binom{x}{j}\)
于是组合意义就是要从\(i\)个中选\(j\)个
用二元生成函数改写一下
于是就等价于
\[\sum_{j=0}^{k-1}f^*_j[y^j]\sum_{i=0}^{+\infty}\frac{((1+y)G(x))^i}{i!}=\sum_{j=0}^{k-1}f^*_j[y^j]e^{(1+y)(-\ln(1-x)-x)} \]令\(F(x,y)=e^{(1+y)(-\ln(1-x)-x)}\)
我们先算出
\[\sum_{j=0}^{k-1}f^*_j[x^j]F(x,y) \]这时我们使用求导大法
\[\begin{aligned} \frac{\partial}{\partial x}F&=(\frac{1}{1-x}-1)(1+y)F\\ &=\frac{x(1+y)}{1-x}F\\ (1-x)\frac{\partial}{\partial x}F&=x(1+y)F\\ \end{aligned} \]令\(f_{n}=[x^n]F(x,y)\)
提取系数
\[(n+1)f_{n+1}-nf_{n}=(1+y)f_{n-1}\\ A_{n+1}=\left( \begin{matrix} \frac{n}{n+1}&1\\ \frac{1+y}{n+1}&0 \end{matrix} \right)\\ \left( \begin{matrix} f_{n+1}&f_{n} \end{matrix} \right)= \left( \begin{matrix} f_{n}&f_{n-1} \end{matrix} \right) A_{n+1} \]于是可以分治\(NTT\)计算，转置的时候只要一点点地转过来就可以了（汗
标签：begin,frac,sum,计数,整理,end,binom,aligned From： https://www.cnblogs.com/AmanoKumiko/p/16884589.html