把所有数数trick统一放在这里好了。
线性求多项式卷积的一项系数，线性插值一项系数
抱歉，这是不可能的。但是请注意$O(n^2)$插值所有系数是不需要法法塔并且容易实现的，就直接把拉插的式子那个prod里面的东西全乘起来，每次除掉其中一项就行了，而这个除法是容易计算的。
如果你的卷积是两个东西卷起来，那么可以直接卷。如果你想求系数的前缀和，那么可以拿一边卷另一边的前缀和。如果数量更多，不能避免法法塔。
我感觉我们需要知道很多不可做的问题。把一个问题归结为一个更广泛的问题很可能会帮助我们，但是我们需要知道每个广泛问题和它们的每个特殊情况，比如线性插值一项系数是不可能的，但是线性求两个多项式卷积的一项系数是可能的，如果本来问题是第二个，但是我们直接钦点使用点值，那么就把可做的问题变成了不可做的。这也说明在线性复杂度求系数的时候，点值并不能帮我们做什么，因为点值和系数之间的转换是困难的。
微积分相关
如果你不求理解只希望先用着，那么请记住这句话 :
我们有
\(\mathcal{A}=\mathrm{SEQ}(\mathcal{B})\Rightarrow A(z)=\displaystyle\frac{1}{1-B(z)}\) 请注意你可以，或者说应当把$\displaystyle\frac{1}{1 − B(z)}$看成$1+B(z)+B^2(z)+B^3(z)+…$的简写。
但是它在代数运算下的行为和你平常见到的$\displaystyle\frac{1}{1-x}$的确一样，比如说有$\frac{1-B(z)}{1-B(z)}=1$。
不如说，因为它有这些性质所以我们才这么简写。
——x义x《组合对象符号化·构造组合类·Sequence构造》
导数写作$y^\prime=\frac{\mathrm{d}y}{\mathrm{d}x}$，是因为$y^\prime\mathrm{d}x=\mathrm{d}y$。(你真的知道微分的定义吗?)
积分写作$\int_a^b f(x)\mathrm{d}x$，而不是$\int_a^b[x] f(x)$之类的，是因为它就是可以和微分$\mathrm{d}x$配合使用(两边加积分号)。
我以前在积分的时候，会在$\mathrm{d}x$前面加一个空格(而写乘法的时候不会)，现在看起来它其实不应该加啊。
求导
当你看到下降幂$n^{\underline{k}}$，想要把它凑出一个封闭形式，可以考虑使用$\left(\frac{\mathrm d}{\mathrm d z}\right)^k z^n=n^{\underline{k}}z^{n-k}$，然后把求导提到外面之类的，这个算子称为$\mathrm D$。这个例题在 两类欧拉积分 里面讲到了。
当你看到普通幂$n^k$，想要把它凑出一个封闭形式，可以考虑使用$\left(z\frac{\mathrm d}{\mathrm d z}\right)^k z^n=n^kz^n$这样的，这个算子称为$\vartheta$。
当你想要展开$\vartheta^k$的时候，手玩一下可以发现它会变成若干个$z^i\mathrm D^i$这样的东西，并且系数是斯特林数。具体一点
\[\vartheta^n=\sum_{k=0}^n{n\brace k}z^k\mathrm D^k\]，当用它搞$n^k$时，对应于把$n^k$展开成下降幂，这可以在下面这个题中体现。
试看看! 例题1.6
联合省选2020 组合数问题
给定$n,x$和$m$次多项式$f$，求
\[\sum_{k=0}^n\binom{n}{k}x^kf(k)\]膜合数的值。$n,x\leq 10^9,m\leq 1000$。
把多项式拆开。
\[\sum_{k=0}^n\binom{n}{k}k^tx^k\]那么这个式子就是刚才我们说的东西。记$\vartheta=x\frac{\mathrm d}{\mathrm d x}$，使用$\vartheta^t$。
\[\begin{aligned} &\sum_{k=0}^n\binom{n}{k}k^tx^k\\ =&\sum_{k=0}^n\binom{n}{k}\vartheta^t x^k\\ =&\vartheta^t\sum_{k=0}^n\binom{n}{k}x^k\\ =&\sum_{i=0}^t{t\brace i}\sum_{k=0}^n\binom{n}{k}k^{\underline{t}}x^k\\ =&\sum_{i=0}^t{t\brace i}\sum_{k=0}^n\frac{n^{\underline{k}}}{k!}k^{\underline{t}}x^k\\ =&\sum_{i=0}^t{t\brace i}\sum_{k=0}^nn^{\underline{t}}\frac{(n-t)^{\underline{k-t}}}{(k-t)!}x^k\\ =&n^{\underline{t}}\sum_{i=0}^t{t\brace i}\sum_{k=0}^n\binom{n-t}{k-t}x^k\\ =&n^{\underline{t}}x^t\sum_{i=0}^t{t\brace i}\sum_{k=0}^{n-t}\binom{n-t}{k}x^k\\ =&n^{\underline{t}}x^t\sum_{i=0}^t{t\brace i}(1+x)^{n-t}\\ \end{aligned}\]最后一步是二项式定理。于是就结束了。复杂度$O(m^2)$。
试看看!例题1.7
ccpc20 final H. Nonsense
相当于，给$n,x_0,y_0,a_L,b_L$，对$a\leq a_L,b\leq b_L$求
\[\sum_i\binom{i}{a}\binom{n-i}{b}x^{i-a}y^{n-i-b}\]$a_L,b_L\leq 5000$。
考虑答案就是$\frac{1}{x_0y_0}[z^{n-a-b+2}]\frac{1}{(1-x_0z)^a(1-y_0z)^b}$。如果$x_0,y_0$至少一个是$0$，很容易$O(1)$算。
这玩意当然有整式递推啊。但是$O(\sqrt{n}\log n)$肯定没法跑2e5组啊。看起来也有线性递推，但是是大约$a+b$阶的。
考虑直接寻找$a,b$上的整式递推，但是这个gf看起来没锤子用，我们希望以$a,b$为两个元的次数搞一个gf，也就是说答案就是它提取$[x^ay^b]$，但是我其实是不太会的，hos.lyric说的好，注意到恰好有$\frac{\mathrm d}{\mathrm d x}x^k=k^\underline{a}x^{k-a}$，可以感觉到这个题就是这么出的，也就是说答案就是
\[\left(\frac{1}{a!b!}\left(\frac{\mathrm d}{\mathrm d x}\right)^a\left(\frac{\mathrm d}{\mathrm d y}\right)^b\sum_ix^iy^{n-i}\right)(x_0,y_0)\]为了转化成提取系数，换元，让$x\leftarrow x+x_0,y\leftarrow y+y_0$，那么就变成代入$(0,0)$了，那么答案就只和$[x^ay^b]\sum\limits_i(x+x_0)^i(y+y_0)^{n-i}$有关。等比数列求和，它就是$\frac{(x+x_0)^{n+1}-(y+y_0)^{n+1}}{(x+x_0)-(y+y_0)}$，这玩意显然有整式递推。
Foata变换
一个排列的轮换分解是，选择一个还未处理的$i$，写下$i,p(i),p(p(i)),…$，直到重新遇到$i$，我们得到了一个环。把所有环写在一起就得到整个排列。
一个排列的标准轮换分解是，对每个环，我们选择其中最大的那个$i$作为第一项，然后把所有环按最大值从小到大排序。那么我们知道标准分解和排列是双射，因为从左往右扫，遇到一个前缀最大值，我们就知道出现了一个新的环。一个标准分解，忽略每个数在哪个环之后也是一个排列，所以它是一个排列到排列的双射。从排列到其标准分解的映射称为Foata变换。
如果一个排列有$k$个超越，那么Foata变换之后它有$k-1$个上升。通过下降幂棋盘多项式分解定理，这也给出了欧拉数的一种计算方法。
逆序对数的gf
它是$1(1+z)(1+z+z^2)…(1+z+…+z^{n-1})=n!_z$。
fkt
平面图完美匹配计数。大家都会算pf，但是pf跟完美匹配数差了一个$\mathrm{sgn}$，所以一个想法是通过给每条边加一个$\pm 1$的权把$\mathrm{sgn}$消掉。考虑把$\pm 1$描述成定向，如果有边$i\rightarrow j$，那么邻接矩阵$A$中$A_{i,j}=1,A_{j,i}=-1$。
那么现在我们定义一个排列的贡献是$f(p)=\mathrm{sgn}(p)\prod A_{p_{2i-1},p_{2i}}$。首先我们知道一个匹配对应的所有排列的贡献相等，因为交换两条匹配边的位置，或者交换一条匹配边的端点的位置都不影响$f$。
结论 如果一个平面图满足，对于每个内部面，其边界上恰有奇数条顺时针方向的边，那么每个完美匹配的贡献都是$1$或者都是$-1$。
证明 好像比较复杂，见唐队长的论文 浅谈平面图相关算法。
感觉这个东西的构造一般不会用到吧。
多次查询组合数行前缀和
简单做法是莫队，因为它在两个方向上都有整式递推。
复杂做法是，考虑线段树每个点$[l,r]$维护关于$x$的多项式$\sum\limits_{i=l}^r\frac{\binom{x}{i}}{\binom{x}{l}}$，可以分治法法塔$O(n\log^2 n)$合并出来。然后把查询扔上去多点求值就仨$\log$啦。具体一点，我们算的大概是$F_u=F_{\mathrm{lc}(u)}+\frac{\binom{x}{l}}{\binom{x}{mid+1}}F_{\mathrm{rc}(u)}$，那个系数就是$\frac{(x-mid-1)^\underline{l-mid-1}}{l^\underline{l-mid-1}}$。
为了优化到$\log^2$，alpha老师之言可谓切綮。考虑一个更一般的问题，我们每个位置有一个每个元都是多项式的大小$O(1)$的矩阵，这里不妨假设每个多项式都是$O(1)$次，否则只要换成加权平衡的分治结构即可。当然所有多项式的次数和和$n$同阶。需要支持每次查询一个前缀矩阵积在某个点的点值。比如$y$维有整式递推，那么$x$维的转移就是关于$x$的元素是多项式的矩阵。
那么我们分治法法塔计算每个点子树中分治取膜多点求值的时候要膜的那个东西，设为$G_u$好了，设$[1,l)$的矩阵积为$P$，那么把$P$膜左儿子的$G$递归到左儿子，$P$乘上左儿子的矩阵积膜右儿子的$G$递归到右儿子。复杂度$O(n\log^2 n)$。
如果同一个前缀有多个查询，可以直接给每个塞一个空位置。
这个东西是，一维是整式递推，另一维是求点值。莫队只能处理两维都是整式递推的情况。
关键是二维整式递推应该如何推
gdkoi2023 D1 B. 错排
求$f(n,m)$表示长$n$的排列，前$m$个位置没有限制，剩下的位置满足$p_i\neq i$的方案数。
写个dp先。如果$m=0$，答案是错排数$d_n$。如果$m>0$，我们枚举$p_1$选了啥，如果选了$1$，递归到$f(n-1,m-1)$。如果没选$1$，那么限制它不能选$1$，递归到$f(n,m-1)$。我们设一个gf $F_m$，那就有$F_m=(1+z)^mD$。
这玩意显然是d-finite的。大家都知道$d_n=(n-1)(d_{n-1}+d_{n-2})$，对应到微分方程也就是$D=z^2D^\prime+z^3D^\prime+z^2D$这样的，或者说$D^\prime=\frac{1-z^2}{z^2+z^3}D$，而设$G=(1+z)^m$，有$G^\prime=\frac{m}{1+z}G$，那么我们知道它们的乘积也有一个微分方程，它就是$(DG)^\prime=\left(\frac{1-z^2}{z^2+z^3}+\frac{m}{1+z}\right)DG$。这是一个沿$n$的二阶整式递推。
那么接下来考虑沿$m$的。需要先求一个固定$n$的gf，一个想法是强行塞一个元$t$变成$T=\frac{D}{1-(1+z)t}$，那么答案就是$[z^nt^m]$了，然后提取$[z^n]$
\[[z^n]\frac{D}{1-(1+z)t}=\sum_id_{n-i}\sum_j\binom{j}{i}t^j\]这个式子感觉并不简单，大概不如我们直接容斥。钦点$k$个位置连了自己，我们得到
\[\sum_it^i\sum_k(-1)^k\binom{n-i}{k}(n-k)!=\sum_it^i(n-i)!\sum_{k=0}^{n-i}\frac{(-1)^k(n-k)!}{k!(n-i-k)!}\]这个$(n-i)!$是好处理的，移动的时候除掉再乘回来即可。里边这个$\sum$是啥呢，有一个$(n-i-k)!$跟$i$相关就不是很好，不过还是可以看出它就是$[t^{n-i}]e^t\sum\limits_k\frac{(-1)^k(n-k)!}{k!}t^k$。右边看起来很像超几何级数，因此很d-finite。$A=e^z$满足$A^\prime=A$，$B=\sum\frac{(-1)^k(n-k)!}{k!}t^k$满足$b_k=-(k+1)(n-k)b_{k+1}$，也就是$B=-nB^\prime+tB^{\prime\prime}$。接下来
\[\begin{aligned} (AB)^\prime&=A(B+B^\prime)\\ (AB)^{\prime\prime}&=A(B+2B^\prime+B^{\prime\prime})\\ &=A((1+\frac{1}{t})B+(2+\frac{n}{t})B^\prime) \end{aligned}\]也就是$(AB)^{\prime\prime}=(2+\frac{n}{t})(AB)^\prime-(1+\frac{n-1}{t})AB$。
这里由于固定$m$的gf递推非常简单，只需要这个沿$m$的整式递推就很容易做到$O(n\sqrt{n})$。
counting constraint satisfaction problem(#csp)/holant problem
The Complexity of Complex Weighted Boolean #CSP。
#csp: 有一些bool变量$X$，有一些这些变量上的函数$F$，定义一种对每个变量的赋值方案的权值是所有函数值的乘积，求所有方案的权值和。
holant problem: 图，每条边上有一个bool变量，每个点有一个邻边的函数$F$，定义一种对每个变量的赋值方案的权值是所有函数值的乘积，求所有方案的权值和。
如果不考虑图的特殊性质，两个东西是等价的。显然holant problem是#csp的特例，而#csp可以通过给每个函数建一个点，每个变量建一个点，不妨认为函数是左部而变量是右部。函数和对应的变量连边，变量上有一个函数保证它的邻边都相等否则没有贡献，来归约到holant problem。
看起来这个牛逼论文证明了这两类问题可做的充要条件。
holant problem
我们定义$[a,b]$表示把$0$映射到$a$，$1$映射到$b$的函数，$[a,b]^k$是它的$k$次笛卡尔积。
忽略常系数，设$\alpha$是$1,-1,i,-i$之一，那么一个固定$F$的holant problem是p的，当且仅当每个$F$都是以下三种情况之一
-
$[1,0]^k+\alpha[0,1]^k$
-
$[1,1]^k+\alpha[1,-1]^k$
-
$[1,i]^k+\alpha[1,-i]^k$
各$\alpha$可以不同。否则它是#p-complete。我们将它们分别称为第一二三类好了。
我们来举几个例子。在第一类中，取$\alpha=1$，也就是每个点所有邻边相同。取$\alpha=-1$，也就是邻边全$0$贡献$1$，全$1$贡献$-1$。
在第二类中，取$\alpha=1$，也就是如果邻边中有$c$个$1$，贡献$(-1)^c+1=2[c\text{ is even}]$，如果每个点的$F$都是这个，这就是欧拉生成子图计数。
不过不知道这玩意有啥应用啊。可能是不是还得再找一篇论文!
#csp
一个固定$F$的#csp是p的，当且仅当忽略常系数后，$F$们是以下两种情况之一
-
每个$F$都是一元函数和某两个变量相等/不等的函数的乘积。
-
每个$F$都是这样的 : 把各$x$和一个$1$拼起来得到一个向量$X$，有一个线性方程组$AX=0$，一组$X$上系数在$\mathbf{Z}_2$的仿射函数$L_i$(也就是说它是若干个$X$中的元素xor起来)，$F=[AX=0]i^{\sum L_i(x_1,…,x_k)}$，其中$i=\sqrt{-1}$，且指数上的$\sum$在$\mathbf{Z}_4$中计算。
前者是简单的，接下来只考虑后者。注意到$F$对乘法封闭，也就是说我们现在只有一个$F$了。
先把每个函数的$[AX=0]$扔掉。我们找到解空间的一个基，那么每个解都可以表示成这些向量的线性组合，那么每个仿射函数都可以变成这个线性组合的系数们上的函数。以下我们假设没有$[AX=0]$。
引理1 定义$F^{x_i=a}(x_1,…,x_{i-1},x_{i+1},…)$是钦点$x_i=a$得到的函数。对于一个$F(x_1,…,x_k)$，以下两种情况中恰好一种成立 :
-
$\frac{F^{x_1=1}}{F^{x_1=0}}=c$，其中$c$是$1,-1,i,-i$之一的常数。
-
存在一个$x_2,…,x_k$上的$k-2$维仿射子空间$S$，满足其中$\frac{F^{x_1=1}}{F^{x_1=0}}=c$，其外$\frac{F^{x_1=1}}{F^{x_1=0}}=-c$，其中$c$是$1,i$之一的常数。
考虑$x_1$在其中系数为$0$的那些$L_i$是可以不管的。那么剩下的$L_i$都有$L_i^{x_i=0}$和$L_i^{x_i=1}$相反。那么$\displaystyle\frac{F^{x_1=1}}{F^{x_1=0}}=i^{\sum\limits_i(1-2L_i^{x_i=0})}$，其中$i$枚举$x_1$在其中系数为$1$的$L_i$。设这样的$i$有$m$个，它就是$i^m(-1)^{\sum\limits_i L_i^{x_i=0}}$，那么那个$\sum$现在可以膜$2$而不是膜$4$了，那么所有的仿射函数都可以xor起来合成一个了，这就给出那个$k-2$维仿射子空间$S$。
但是还有这个仿射函数恒为$0$的情况。此时就是case 1。这就结束了。
接下来我们给出算法。
如果满足引理1中的case 1，我们直接把答案乘上$1+c$，并把$x_1$赋为$0$递归下去。
如果满足引理1中的case 2。答案就是$\sum\limits_{x_2,…\in S}(1+c)F^{x_1=0}(x_2,…)+\sum\limits_{x_2,…\in\overline{S}}(1-c)F^{x_1=0}(x_2,…)$。如果$c=1$，只有前者有贡献。如果$c=i$，注意到$1+i=i(1-i)$，这启发我们附上一个新的函数$L^\prime$凑出那个$i$并递归下去，然后就可以整个乘$(1-i)$了。这个函数应该在引理1中那个$S$中的点处是$1$，$\overline{S}$处是$0$。于是就结束了。
为了判断是哪个case，和证明一样做，把所有包含$x_1$的$L$找出来，看它们的xor和$G$是不是除了$x_1$的系数都是$0$，如果是就是case 1，否则就是case 2。容易计算引理1中的$m$，于是往$G$代入全$0$就可以计算$c$，同时也可以知道$S$是$G=0$还是$G=1$的。这里甚至不需要四进制bitset。
那么我们考虑一个例子。图，计算有多少导出子图边数是偶数。学这个就是因为见到了这个题。
我们让每条导出子图中的边贡献$-1$，那么每条边就是$(-1)^{x_ux_v}$，凑一个$x_ux_v=\frac{(x_u+x_v)^2-x_u^2-x_v^2}{2}$，膜$2$下平方就是没有，那就是$i^{x_u\operatorname{xor}x_v+3x_u+3x_v}$了。所以每条边是$7$个函数。计算$S$的时候涉及的函数只有前面生成的$O(n)$个$L^\prime$和当前点的邻接点，压位一下复杂度就是$O(\frac{n^3}{w})$。
对这个问题有一个消元角度的解释，但是我不知道对于其它的能否这么做。
zjoi2018 树
x义x说的好。
先把期望变成数数。考虑我们枚举一个无标号有根树，然后分配标号。那么对于一个$n$个点的无标号有根树，设有$w$种方案给它分配标号使得每个点比父亲大，它的贡献就是$w^k$。
考虑怎么算$w$，根必然是$1$，根的子树之间可以随意插，也就是说如果dp一下的话，$w(u)=(\mathrm{size}(u)-1)!\prod\limits_v\frac{w(v)}{\mathrm{size}(v)!}$。考虑构造一个gf，一棵大小为$s$的树对$z^s$项贡献$\frac{w^k}{(s!)^k}$，那么它的乘法就对应卡笛尔积。
考虑怎么算$w^k$的和，根必然是$1$，所以把子树都乘起来之后塞一个根的效果就是乘$z$以平移一位。根的子树之间可以随意插，但是如果子树同构那就不能随意插了，这里有个经典的euler变换或者polya exp，我们枚举同构的子树用了$t$个，分配标号的时候就要除一个$(t!)^k$。那么也就是说左边是去掉根的树，然后一棵树对右边的贡献是$\displaystyle\sum\limits_i\frac{\left(\frac{w^kz^s}{(s!)^k}\right)^i}{(i!)^k}$，我们要把右边这些东西都乘起来。这里感觉上不容易合并不同的树，我们先枚举一棵树$T$看看
\[F=z\prod_T\sum_i\frac{\left(\frac{w^k(T)z^{s(T)}}{(s(T)!)^k}\right)^i}{(i!)^k}\]直接乘完全没法拆，考虑$\ln-\exp$，我们得到
\[F=z\exp\sum_T\ln\sum_i\frac{\left(\frac{w^k(T)z^{s(T)}}{(s(T)!)^k}\right)^i}{(i!)^k}\]这个$\ln$看起来也不是很好直接算。我们考虑哪里可以拆出一个$F$来以递归下去，如果算出$\ln$然后换个求和号看起来就好了，因为不会直接算，我们尝试爆力设出$\ln$的结果 :
\[\ln\sum_i\frac{z^i}{(i!)^k}=\sum_ic_iz^i\]那么上面就变成
\[\begin{aligned} F&=z\exp\sum_ic_i\sum_T\left(\frac{w^k(T)z^{s(T)}}{(s(T)!)^k}\right)^i\\ &=z\exp\sum_ic_i\sum_T\frac{w^{ki}(T)z^{s(T)i}}{(s(T)!)^{ki}} \end{aligned}\]看起来此时右边跟$F$很像。我们让答案是$F_1(z)$，右边这样的东西是$F_i(z^i)$，这就赢了。
此时看起来会递归到很多$F$啊。不过注意到$z$的次数超过$n$就没有意义啦，而这个下标和次数是一起增长的，所以$F_t$也只在$t\leq n$的时候有用，并且只有$\frac{n}{t}$项有用。考虑复杂度，$\exp$右侧的贡献只有$O(n\log n)$次，所以这是$O(n^2)$的。
还有那个算$\ln$，使用$O(n^2)$的$\ln$，我们需要算$n,\frac{n}{2},\frac{n}{3},…$项的$\ln$，复杂度还是$O(n^2)$。所以这个题也是容易做到$O(n\log^2 n)$的。
如果你感觉中间的过程有点离奇，感觉不知道能产生什么效果就这么去做了，有一个更为震撼的解释是 https://www.luogu.com.cn/blog/ftiasch/solution-p4500 。
$q$-analog
很复杂的一类gf，因为严格比普通的gf复杂/cf。你经常在分拆，子空间，逆序对，以及加奇怪权的经典组合问题等地方看到它。
定义$n_q=\frac{1-q^n}{1-q}$，$n! _ q=\prod\limits_{i=1}^ni _ q$，类似可以定义下降幂${n^\underline{k}}_q$。于是可以定义$q$-二项式系数$\binom{n}{k} _ q=\frac{ {n^\underline{k}}_q}{k!_q}$。称为$q$-analog，是因为我们取$q\rightarrow 1$时就能得到一个不带$q$的经典等式。
练习 : 证明以下 加法公式 上指标反转 上指标求和 范德蒙德卷积 的$q$-analog。
\[\begin{gathered} \binom{n}{k}_q=q^k\binom{n-1}{k}_q+\binom{n-1}{k-1}_q=\binom{n-1}{k}_q+q^{n-k}\binom{n-1}{k-1}_q\\ \binom{n}{k}_q=(-1)^kq^{kn-\binom{k}{2}}\binom{k-n-1}{k}_q\\ \binom{n+1}{m+1}_q=\sum_{k=0}^nq^{(m+1)(n-k)}\binom{k}{m}_q=\sum_{k=0}^nq^{k-m}\binom{k}{m}_q\\ \binom{n+m}{k}=\sum_iq^{(n-k)(k-i)}\binom{n}{i}_q\binom{m}{k-i}_q \end{gathered}\]然后我们看看最为重要的结论，$q$-二项式定理。定义$q$-pochhammer为
\[(z;q)_n=\prod_{i=0}^{n-1}(1-q^iz)\]它本身是$(1-z)^n$的$q$-analog，并且可以看出它跟阶乘幂也有些关系，有$\frac{(q^n;q)_k}{(1-q)^k}={n^\overline{k}}_q$，当然还有$n! _ q=\frac{(q;q) _ n}{(1-q)^n},\binom{n}{k} _ q=\frac{(q;q) _ n}{(q;q) _ k(q;q) _ {n-k}}$。这个形式在整数分拆之类的问题中常常出现。下面是$q$-二项式定理
\[(z;q)_n=\sum_{i=0}^n(-1)^iq^\binom{i}{2}\binom{n}{i}_qz^i\]考虑如何证明这东西，一个经典且重要的扰动是$(qz;q)_n=\frac{1-q^nz}{1-z}(z;q)_n$，那么直接提取$[z^k]$，我们得到
\[\begin{aligned} [z^k](qz;q)_n-[z^{k-1}](qz;q)_n&=[z^k](z;q)_n-q^n[z^{k-1}](z;q)_n\\ q^k[z^k](z;q)_n-q^{k-1}[z^{k-1}](z;q)_n&=[z^k](z;q)_n-q^n[z^{k-1}](z;q)_n\\ [z^k](z;q)_n&=\frac{q^{k-1}-q^n}{q^k-1}[z^{k-1}](z;q)_n \end{aligned}\]显然$[z^0] (z;q) _ n=1$，那么$[z^k] (z;q) _ n=\prod\limits _ {i=1}^k q^{i-1}\frac{1-q^{n-i+1}}{q^i-1}=(-1)^iq^\binom{k}{2}\frac{ {n^\underline{k}}_q}{k! _ q}$。
另一个常用的式子是$n=\infty$的情况，此时求个极限可以知道$\binom{\infty}{i}_q=\frac{1}{(q;q)_i}$，也就是说
\[(z;q)_\infty=\sum_{i=0}^\infty(-1)^i\frac{q^\binom{i}{2}}{(q;q)_i}z^i\]有趣的是这玩意跟 子空间反演 有关，你会把$q$代入一个真实值。
另一个不那么常用的式子。考虑$n$为负数的情况，我们用$(z;q) _ n=(1-q^{n-1}z)(z;q) _ {n-1}$来定义它，那么可以知道
\[(z;q)_{-n}=\prod_{i=-n}^{-1}\frac{1}{1-q^iz}=\frac{1}{q^\binom{n+1}{2}}\prod_{i=1}^n\frac{1}{q^i-z}\]它也满足$(qz;q)_n=\frac{(1-q^nz)}{(1-z)}(z;q)_n$，因此$q$-二项式定理仍然成立
\[(z;q)_{-n}=\sum_{i=0}^\infty(-1)^iq^\binom{i}{2}\binom{-n}{i}_qz^i\]那么$\binom{-n}{i}_q$是啥?使用刚才的上指标反转，可以知道负指数的$q$-二项式定理即为
\[(z;q)_{-n}=\sum_{i=0}^\infty(-1)^iq^{-ni}\binom{i-n-1}{i}_qz^i\]loj6077 2017 山东一轮集训 Day7 逆序对
大家都知道答案就是$[z^k]n! _ z$，考虑依次插入每个数，第$i$个数可以自由选择产生$0,…,i-1$个逆序对即可。$n! _ z=\frac{(z;z) _ n}{(1-z)^n}$，那么要计算$(z;z) _ n$，直接用$q$-二项式定理展开它，我们得到$\sum\limits _ iz^\binom{i+1}{2}\binom{n}{i} _ z$，$z^\binom{i+1}{2}$让它只有前$O(\sqrt{n})$项有贡献，而$\binom{n}{i} _ z=\frac{(z;z) _ n}{(z;z) _ i(z;z) _ {n-i}}$。虽然这里有个$(z;z) _ n$但是影响不大，因为$\binom{n}{0} _ z=1$，而$i$到$i+1$的时候就是乘了一个$\frac{1-z^{n-i}}{1-z^{i+1}}$。复杂度$O(n\sqrt{n})$。
ahoi2022 山河重整
首先有个经典结论是从小到大加数，如果现在极长可行前缀是$[1,k]$，那么加入一个$t\leq k+1$会让前缀变成$[1,k+t]$，否则$k+1$就不可能凑出来了。
考虑容斥，钦点第一个凑不出来的数，那么比它小的都能凑出来，dp，设$dp(i)$表示$\leq i$的数选一些，能凑出的极长前缀恰好是$[1,i]$的方案数，那么看起来我们计算总和是$i$的方案数，这样必然凑不出$i+1$，然后减去$i$以内有数凑不出来的方案数即可，统计答案则直接用所有方案减去$dp(i<n)$。枚举第一个凑不出来的数$k$，那么小的部分就是$dp(k-1)$，此时总和是确定的$k-1$，然后$[k+1,i]$中要凑出$i-k+1$。直接写成gf
\[f_n=[z^n]\left(\prod_i(1+z^i)-\sum_{k=1}^{n-1} f_{k-1}z^{k-1}\prod_{i=k+1}(1+z^i)\right)\]看看能不能消掉右边$\sum$的上限$n-1$。首先这个上限可以改成$n$，然后把左边移过去，就非常好了，我们得到
\[\prod_i(1+z^i)=\sum_k f_{k-1}z^{k-1}\prod_{i=k+1}(1+z^i)\]左边是分拆数，可以$O(n\sqrt{n})$计算，目前主流方法大概是枚举durfee square的边长。右边那个$\prod$如果不贡献$1$则会让指数至少翻倍，所以可以倍增一下，问题变成算$\sum_{k=1}^l f_{k-1}z^{k-1}\prod\limits_{i=k+1}(1+z^i)\bmod{2l}$之类的东西，这样位置$\geq l$的$f$贡献系数都是$1$可以直接确定。
这个$\prod$看着就很离谱。看起来经典的，它就是$(z^{k+1};z)_\infty$，套用$q$-二项式定理 :
\[\sum_{k=1}^l f_{k-1}z^{k-1}\sum_i\frac{z^{\binom{i}{2}+(k+1)i}}{(z;z)_i}\]直接枚举$i$，每次是平移一下然后卷一个$\frac{1}{1-z^i}$，因为$i$只到$O(\sqrt{n})$，复杂度$O(n\sqrt{n})$。于是这又可以写成元素是多项式的矩阵链求积了，我们对$k\leq K$分治法法，复杂度$\tilde{O}(K^2)$，大的部分$i$则只到$O(\frac{n}{K})$，复杂度$O(\frac{n^2}{K})$，平衡一下我们得到$\tilde{O}(n^\frac{4}{3})$。
候选队胡策2022 理论复杂度
组合意义天地灭题。
考虑枚举$r$的权值，然后从小往大考虑每个数放多少，我们可以得到
\[\sum_kz^k\left([t^{r-1}]\prod_{i=k}\frac{t}{1-z^i}\right)\left(\prod_{i=1}^k\frac{1}{1-z^i}\right)^2\]这个$t^{r-1}$就很不好。这是一个$r-1$个，每个$\geq k$的分拆，提出$z^{(r-1)k}$，经典地把ferrers图转置一下，我们就得到一个
\[\begin{aligned} &\sum_kz^{rk}\left(\prod_{i=1}^r\frac{1}{1-z^i}\right)\left(\prod_{i=1}^k\frac{1}{1-z^i}\right)^2\\ =&\left(\prod_{i=1}^r\frac{1}{1-z^i}\right)\sum_kz^{rk}\prod_{i=1}^k\frac{1}{(1-z^i)^2} \end{aligned}\]左边是简单的，考虑怎么算右边。看起来这是个分拆数的平方，经典地我们乘两个$\prod\limits_{i=1}^\infty(1-z^i)$上去，问题变成计算$\sum\limits_kz^{rk}\prod\limits_{i=k+1}^\infty(1-z^i)^2$，而根据广义五边形数定理，乘除$\prod\limits_{i=1}^\infty(1-z^i)$是容易$O(n\sqrt{n})$的，或使用法法塔做到$O(n\log n)$。
大家都知道$q$-二项式定理，这里右边这个就是
\[\begin{aligned} {(z^{k+1};z)_\infty}^2=&\left(\sum_i(-1)^i\frac{z^\binom{i}{2}}{(z;z)_i}z^{(k+1)i}\right)^2\\ =&\left(\sum_i(-1)^i\frac{z^{\binom{i+1}{2}+ki}}{(z;z)_i}\right)^2 \end{aligned}\]代入，然后如果没有这个平方那就直接换求和号，$k$就一个等比数列求和搞没啦，但是很遗憾它有平方，尝试爆力展开
\[\begin{aligned} &\sum_kz^{rk}\left(\sum_i(-1)^i\frac{z^{\binom{i}{2}+(k+1)i}}{(z;z)_i}\right)^2\\ =&\sum_i(-1)^i\frac{z^\binom{i+1}{2}}{(z;z)_i}\sum_j(-1)^j\frac{z^\binom{j+1}{2}}{(z;z)_j}\sum_kz^{(i+j+r)k}\\ =&\sum_i(-1)^i\frac{z^\binom{i+1}{2}}{(z;z)_i}\sum_j(-1)^j\frac{z^\binom{j+1}{2}}{(z;z)_j}\frac{1}{1-z^{i+j+r}} \end{aligned}\]转而枚举$i+j$。
\[\begin{aligned} =&\sum_k(-1)^k\frac{1}{1-z^{k+r}}\sum_{i+j=k}\frac{z^\binom{i+1}{2}z^\binom{j+1}{2}}{(z;z)_i(z;z)_j}\\ =&\sum_k(-1)^k\frac{1}{1-z^{k+r}}[t^k]\left(\sum_i\frac{z^\binom{i+1}{2}}{(z;z)_i}t^i\right)^2\\ =&\sum_k(-1)^k\frac{1}{1-z^{k+r}}[t^k]{(t;z)_\infty}^2 \end{aligned}\]我们知道$[t^k]{(t;z)_\infty}^2$的$z$的最低次项次数至少是$z^\binom{k+1}{2}$，所以只有$O(\sqrt{n})$的$k$有贡献。好消息是$t$维有整式递推。还是使用经典的扰动，我们知道${(t;z) _ \infty}^2={(zt;z) _ \infty}^2(1-tz)^2$，两边提取$[t^k]$就得到$[t^k]{(t;z) _ \infty}^2=[t^k]{(zt;z) _ \infty}^2-2z[t^{k-1}]{(zt;z) _ \infty}^2+z^2[t^{k-2}]{(zt;z) _ \infty}^2$，也即$[t^k]{(t;z) _ \infty}^2=\frac{z^k}{1-z^k}(-2[t^{k-1}]{(t;z) _ \infty}^2+[t^{k-2}]{(t;z) _ \infty}^2)$。于是爆力即可，复杂度$O(n\sqrt{n})$。
如果允许法法，可以写成一个元素为多项式的矩阵链求积的问题，这里多项式总次数是$O(n+r\sqrt{n})$的，分治法法即可做到$\tilde{O}(n+r\sqrt{n})$。当$r$很大的时候，我们直接算最开始那个式子就是$\tilde{O}(\frac{n^2}{r})$，平衡一下得到$\tilde{O}(n^\frac{5}{4})$。
集训队胡策22 R5 C. 核
见 线性代数。
bm
求最短线性递推式。
维护一个前缀的最短线性递推式$F_i$，它看起来是$F_i(k)=\sum\limits_i a_{k-i}c_i$这样的，其中$c_0=1$，那么如果总是有$F_i=0$说明它是对的。如果到了$i$这里$F_{i-1}$出问题了，它不等于$0$了，设它变成了$d_i$，我们就希望给$F_i$补上$-d_i$。补上的部分显然应该只在$i$是$-d_i$，剩下的地方都是$0$。于是我们找到之前出问题的某个地方，设为$j$，那么$F_{j-1}$应该只在$j$处是$d_j$，所以我们考虑把$F_{j-1}$平移$i-j$位(往中间塞$i-j$个$0$)，它就在$i$处是$d_j$啦，然后把它乘上$-\frac{d_i}{d_j}$，和$F_{i-1}$相加得到$F_i$。为了让阶最小，我们选择$i-j+\deg F_{j-1}$最小的那个，于是只需要维护当前最小的，空间复杂度是线性。
那么如何证明这玩意是对的呢。假设$F$是正确的最短线性递推式，设$G=F_i-F_{i-1}$，那么$G$只在$i$是$-d_i$，也就是说它必然是前面的一个正确的线性递推式。
我打算看看adamant的所有blog啊。
legendre多项式，Solving the “simple math problem” with generating functions
大家都知道$[z^n]\frac{1}{\sqrt{1-4z}}=\binom{2n}{n}$。
现在我们要给出
\[\sum_{i,j}\binom{i+j}{i}^2x^iy^j\]的封闭形式。转而枚举$i+j$
\[\begin{aligned} &\sum_k\sum_i\binom{k}{i}^2x^iy^{k-i}\\ =&\sum_k[t^k]\left(\sum_i\binom{k}{i}x^it^i\right)\left(\sum_i\binom{k}{i}y^it^i\right)\\ =&\sum_k[t^k](xt+1)^k(yt+1)^k \end{aligned}\]遇到了僵局。现在看起来只有一件事可以干了，也就是考虑$(xt+1)(yt+1)=(xyt^2+(x+y)t+1)$，我们尝试用另一种方法把$t$消去，那么重写为$(t(xyt+x+y)+1)$并展开 :
\[\begin{aligned} =&\sum_k[t^k]\sum_i\binom{k}{i}t^i(xyt+x+y)^i\\ =&\sum_k\sum_i\binom{k}{i}[t^{k-i}](xyt+x+y)^i\\ =&\sum_k\sum_i\binom{k}{i}x^{k-i}y^{k-i}\binom{i}{k-i}(x+y)^{2i-k}\\ =&\sum_k\sum_i\binom{k}{k-i,k-i,2i-k}x^{k-i}y^{k-i}(x+y)^{2i-k} \end{aligned}\]这是明示我们转而枚举$k-i$啊。
\[=\sum_k\sum_i\binom{k}{i,i,k-2i}x^iy^i(x+y)^{k-2i}\]这样看起来就清爽了一些。我们把$\binom{k}{i,i,k-2i}$写成$\binom{k}{2i}\binom{2i}{i}$，现在可以看到中心二项式系数了。这是为了把$i$换到外面
\[\begin{aligned} =&\sum_i\binom{2i}{i}x^iy^i(x+y)^{-2i}\sum_k\binom{k}{2i}(x+y)^k\\ =&\sum_i\binom{2i}{i}x^iy^i(x+y)^{-2i}\frac{(x+y)^{2i}}{(1-x-y)^{2i+1}}\\ =&\sum_i\binom{2i}{i}\frac{x^iy^i}{(1-x-y)^{2i+1}}\\ =&\frac{1}{(1-x-y)\sqrt{1-4\frac{xy}{(1-x-y)^2}}}=\frac{1}{\sqrt{(1-x-y)^2-4xy}} \end{aligned}\]这就是赢了。
那么让我们回到这个题，我们要算$\frac{1}{(1-x-y)\sqrt{(1-x^2-y^2)^2-4x^2y^2}}$。注意到$(1-x^2-y^2)^2-4x^2y^2=(1-x^2-y^2-2xy)(1-x^2-y^2+2xy)=(1-(x+y)^2)(1-(x-y)^2)=(1-x-y)(1+x+y)(1-x+y)(1+x-y)$，那么我们上下同乘$(1+x+y)(1-x+y)(1+x-y)$，就得到$\frac{(1+x+y)(1-x+y)(1+x-y)}{((1-x-y)(1+x+y)(1-x+y)(1+x-y))^\frac{3}{2}}$。上面的部分相当于多次提取，问题是如何提取下面，一个想法是我们已经知道$\frac{1}{((1-x-y)(1+x+y)(1-x+y)(1+x-y))^\frac{1}{2}}$的展开式，可以用它的导数凑出$\frac{1}{((1-x-y)(1+x+y)(1-x+y)(1+x-y))^\frac{3}{2}}$。
但是我们想起它们都是$x^2,y^2$的函数，所以不如看$\frac{1}{((1-x-y)^2-4xy)^\frac{1}{2}}$的导数，对$x$求导得到$-\frac{1}{2}\frac{(-2(1-x-y)-4y)}{((1-x-y)^2-4xy)^\frac{3}{2}}=\frac{1-x+y}{((1-x-y)^2-4xy)^\frac{3}{2}}$，对$y$求导得到$1+x-y$对吧，这俩加起来正好消掉了分子上的$x,y$，所以就结束了。
这里能消掉看起来是一个巧合。如果不能消掉，我们也可以得到两个方向的整式递推。你可能会想到极端情况是这俩求导之后结果相同，我感觉这说明它是$0$啊。
legendre多项式的结论是，设第$n$个legendre多项式是
\[P_n=\frac{1}{2^n}\sum_k\binom{n}{k}^2(z+1)^k(z-1)^{n-k}\]，那么有
\[\sum_n P_nt^n=\frac{1}{\sqrt{1-2zt+t^2}}\]就是这样!
Useful substitutions with generating functions
Example 2. 对$n=1,…,m$，计算$z^n^n$。
嗯展开。
\[\begin{aligned} &[z^n]\sum_i\binom{n}{i}z^{2i}\sum_j\binom{n-i}{j}z^j\\ =&\sum_i\binom{n}{i}\binom{n-i}{n-2i}\\ =&\sum_i\binom{n}{i,i,n-2i}\\ =&\sum_i\binom{n}{2i}\binom{2i}{i} \end{aligned}\]这样就又看到中心二项式系数了。现在加入元$n$
\[\begin{aligned} &\sum_nt^n\sum_i\binom{n}{2i}\binom{2i}{i}\\ =&\sum_i\binom{2i}{i}\sum_nt^n\binom{n}{2i}\\ =&\sum_i\binom{2i}{i}\frac{t^{2i}}{(1-t)^{2i+1}}\\ =&\frac{1}{(1-t)\sqrt{1-4\frac{t^2}{(1-t)^2}}} \end{aligned}\]显然它是代数的，因此也是d-finite的。
另一个做法是逆用拉格朗日反演。拉格朗日反演说
\[[z^n]H(F)=[z^n]H\frac{zG^\prime}{G}\left(\frac{z}{G}\right)^n\]考虑凑出右边的形式，那么这里$\frac{z}{G}=1+z+z^2$，也就是说$G=\frac{z}{1+z+z^2}$，那么$G^\prime=\frac{1-z^2}{(1+z+z^2)^2}$，$\frac{zG^\prime}{G}=\frac{1-z^2}{(1+z+z^2)}$，所以$H=\frac{1+z+z^2}{1-z^2}$。考虑$G$的复合逆$F$，有$\frac{F}{1+F+F^2}=z,zF^2+(z-1)F+z=0$，解得$F=\frac{1-z\pm\sqrt{1-2z-3z^2}}{2z}$，显然根号里面的常数项是$1$，分子的常数项如果消不掉这就不是多项式了，所以应该取减号对吧。那么答案是$H(F)$，所以又所有东西都是代数的了。根据$F$的定义它就是$\frac{F}{z(1-F^2)}=\frac{F}{(z-1)F+2z}=\frac{1-z-\sqrt{1-2z-3z^2}}{(z-1)(1-z-\sqrt{1-2z-3z^2})+2z}=\frac{}{}$。
egf
今天我们学习一下egf相关内容!首先尝试推一下斯特林数的egf。
众所周知，$z^{\overline{n}}=\sum\limits_k{n\brack k}z^k$，这是第一类斯特林数行的egf。证明考虑${n\brack k}$是把$n$个球分进$k$个非空环的方案数对吧，那么上升幂是$z(z+1)…(z+n-1)$，每次选$z$就是放进一个新的环，选常数就是选择一个已经放好的球放在它后面。
考虑第一类斯特林数列。考虑用egf把元素分进环里，那么长$k$的环有$(k-1)!$种方案，而egf的时候除了一个$k!$，那么它的系数其实是$\frac{1}{k}$，所以这是$\ln \frac{1}{1-z}=\sum\limits_i\frac{z^i}{i}$。答案就是$\frac{1}{k!}\left(\ln\frac{1}{1-z}\right)^k$，$\frac{1}{k!}$是因为环是无序的。所以第二类斯特林数列也是简单的，长$k$的环的系数是$\frac{1}{k!}$，那么答案就是$\frac{1}{k!}(e^z-1)^k$。
考虑第二类斯特林数行。好像我们并没有一个好看的egf。
先不管这些了!让我们来考虑自然数幂和，这里设$S(m,k)=\sum\limits_{n=0}^mn^k$，我们想求出$S(m,…)$的gf。一个想法是拆成组合数，也就是$n^k=\sum\limits_i{k\brace i}\binom{n}{i}i!$，然后我们写其egf，egf是因为它和斯特林数结合的好一些
\[\begin{aligned} &\sum_k\frac{z^k}{k!}\sum_i{k\brace i}i!\sum_{n=0}^m\binom{n}{i}\\ =&\sum_k\frac{z^k}{k!}\sum_i{k\brace i}i!\binom{m+1}{i+1}\\ =&\sum_i\binom{m+1}{i+1}(e^z-1)^i\\ =&\frac{e^{(m+1)z}-1}{e^z-1} \end{aligned}\]但是其实不用这么推，直接把每个数$n$的$e^{nz}$加起来就好了!
这个引出伯努利数$\frac{z}{e^z-1}$。
然后还有一个经典问题是错排，错排也就是说没有大小为$1$的环，它是$e^{\ln\frac{1}{1-z}-z}=\frac{1}{(1-z)e^z}$对吧。
拉格朗日反演
如果$F,G$互为复合逆，且$F,G$都没有常数项，都有一次项，那么
\[[z^n]H(F)=\frac{1}{n}[z^{n-1}]H^\prime\left(\frac{z}{G}\right)^n\]或者
\[[z^n]H(F)=[z^n]HG^\prime\left(\frac{z}{G}\right)^{n+1}\]用来在原幂级数(或它的复合方程)和它的复合逆之间相互转化。可以注意到如果$F$没有常数项且有一次项，那么$G$也必然没有常数项且有一次项，而且$G$必然是个幂级数(没有负次项)。
这两个式子选择哪一个的话，如果需要求常数项则只能选第二个，否则就看$H,G$哪个比较容易求导。
几个简单例子
有标号有根树
我们可以直接从复合方程得到复合逆。非空有标号有根树个数的egf满足$F=ze^F$，也就是说$\frac{F}{e^F}=z$。使用拉格朗日反演
\[n![z^n]F=\frac{n!}{n}[z^{n-1}]e^{nz}=n^{n-1}\]广义二项级数
$\mathcal B_t=1+z\mathcal B_t^t$，求$[z^n]\mathcal B_t^r$。
转而考虑$\mathcal B_t-1$对吧，那么$\frac{\mathcal B_t-1}{(\mathcal B_t-1+1)^t}=z$，也就是说它的复合逆是$\frac{z}{(1+z)^t}$。这里$H=(1+z)^r$，使用拉格朗日反演
\[[z^n]\mathcal B_t^r=\frac{1}{n}[z^{n-1}]r(1+z)^{tn+r-1}=\frac{r}{n}\binom{tn+r-1}{n-1}\]通过吸收可以知道它就是$\frac{r}{tn+r}\binom{tn+r}{n}$。
例题1.7 : 广义指数级数
$\mathcal E_t=e^{z\mathcal E_t^t}$，求$[z^n]\mathcal E_t^r$。
你也可以看看真正的双射大师。https://xyix.github.io/posts/?postname=generalized-binomial-exponential
具体数学上的一个问题是$\binom{tn+r}{n}$的gf是什么。我们首先希望把二项式系数外面的东西消掉，考虑$[z^n]\mathcal B_t^r=\frac{r}{n}\binom{tn+r-1}{n-1}$，那么我们求导就消去了$n$，得到$[z^n]\mathcal B_t^{r-1}\mathcal B_t^\prime=\binom{tn+t+r-1}{n}$。现在还差一个$t-1$，这个好说，把$r$改成$r-t+1$即可，也就是说答案就是$\mathcal B_t^{r-t}\mathcal B_t^\prime$。
问题是$B_t^\prime$是什么，对$\mathcal B_t=1+z\mathcal B_t^t$两边求导，得到$\mathcal B_t^\prime=tz\mathcal B_t^{t-1}\mathcal B_t^\prime+B_t^t$，也就是说$\mathcal B_t^\prime=\frac{\mathcal B_t^t}{1-tz\mathcal B_t^{t-1}}$。所以答案就是$\frac{\mathcal B_t^r}{1-tz\mathcal B_t^{t-1}}$。
这和具体数学上的形式$\frac{\mathcal B_t^r}{1-t+\frac{t}{\mathcal B_t}}$还不太一样，为了转化过去，有$\mathcal B_t^{t-1}=\frac{\mathcal B_t-1}{z\mathcal B_t}$，代入即可。
binomial sum
https://www.luogu.com.cn/blog/EntropyIncreaser/zai-tan-binomial-sum-duo-xiang-shi-fu-ge-cha-zhi-yu-tai-lei-zhan-kai
感觉这个说的很好啊!我们以binomial sum这个题为例来看看。
cf932 E. Team Work 。现在要计算
\[\sum_i\binom{n}{i}i^k\]如果后面是个$k^i$我们立马就会做了，但是它不是，考虑使用egf，它是$[z^k]e^{iz}$，那么也就是
\[[z^k]\sum_i\binom{n}{i}e^{iz}=[z^k](1+e^z)^n\]现在可以多项式快速幂做到$O(k\log k)$。能不能再给力一点啊?
记$F=(1+z)^n,G=e^z$，那么答案就是$[z^k]F(G)$。对$F$在$1$处泰勒展开，这是因为$G=e^z$的常数项是$1$，这样展开可以让无限和变为有限和。让我们看看
\[F(G)=\sum_iF^{(i)}(1)\frac{(G-1)^i}{i!}\]可以看到确实只有$i\leq k$的项有贡献。
考虑如何计算$F^{(i)}(1)$，一个比较自然的想法是代入$1$很困难，如果我们先在右侧复合$z+1$，然后就是代入$0$了，就是每次提取常数项了，此时还是只有$\leq k$次项有贡献。有$F(z+1)=(2+z)^n$，直接展开它即可。
考虑如何计算$z^k^i$。发现不太会啊!换个想法，这里我们说明了找到一个多项式$\mathcal F$满足$\mathcal F$和$F$在$1$处的$0,…,k$阶导数都相同，那么就可以把$F$换成$\mathcal F$计算，两者的不同在于$F$的次数很大而$\mathcal F$的次数$\leq k$。次数$\leq k$的多项式复合$e^z$之后提取一项，问题就是算各$[z^k]e^{iz}=i^k$，线筛即可。复杂度是$O(k)$的。
但是我们如何求出这个$\mathcal F$呢。我们已经找到了$\mathcal F(z+1)=F(z+1)\bmod{z^{k+1}}$，它和$F(z+1)$在$0$处的$0,…,k$阶导数都相同，那么再复合$z-1$即可。问题是如何线性地复合$z-1$，注意到$F$是d-finite的，$z-1,z+1$都是代数的，那么$F(z+1)\bmod{z^{k+1}}$还是常数阶d-finite的，只是我们会在常多项式项上补一些东西，使得跨过$z^{k+1}$时把多余的项消成$0$。也就是说我们递推到$z^{k+1}$上$O(1)$项就可以构造出这个整式递推了。然后直接复合$z-1$即可。
注意到一般的gf复合$z-1$是不太好线性的(但是可以一次卷积)。看起来我们已经做的不错了!
然后看几个例题吧。
bell数。计算
\[[z^n]e^{e^z-1}\]$F=e^{z-1},G=e^z$。$F$显然还是d-finite的。
cf392 C. Yet Another Number Sequence 。$F=\frac{1}{1-z-z^2},G=e^z$。这里$F$甚至是有理分式。
部分分式
https://www.luogu.com.cn/blog/EntropyIncreaser/fen-shi-fen-xie-gei-xiao-peng-you-men-zuo-xian-chang-di-biao-yan
感觉不太需要我再重新描述了。
欧拉数
速通!
特殊的数 中最复杂的一个。一会我们将挑战 Slime and Sequences，新年的军队，另一个欧拉数问题。
Slime and Sequences
这他妈啥。考虑怎么算有多少好的序列，容斥，钦点一些$k$完全在$k-1$之前，这会形成一些链，链之间是独立的可以直接egf插起来，一个数当然是$e^z-1$，一条长$k$的链是，如果有$c$个数，那么插板，有$\binom{c-1}{k-1}$种方案划出$k$个数，所以其egf是$\sum\limits_i\binom{i-1}{k-1}\frac{z^i}{i!}=\frac{1}{(k-1)!}\sum\limits_i\frac{z^i}{(i+k)i!}$，看起来不是很好，不过关系不大，我们再枚举长度，套上$\frac{1}{1-z}$，提取$z^n$项即可。
那么现在要固定一个数，感觉这个性质有点太差了啊。换个想法，考虑为什么这个题跟欧拉数有关系啊，我们考虑从左往右扫一个排列$p$，维护当前的数值$c$，初始$c=1$。如果$p_i>p_{i-1}$，做$c\leftarrow c+1$；然后我们在$p_i$位置放一个$c$，这就给出了排列和好序列的双射，也就是说有$k$种数的好序列个数和有$k$个上升的排列个数是相等的，所以上一段我们算了一个$n!$，多少有点乐了。现在可以固定一个数$k$了，我们枚举它的一个出现位置$p$，要在这里出现的话，要让前面有恰好$k-1$个上升，而后面随意，那么也就是
\[\begin{aligned} &\sum_p\binom{n}{p}\genfrac\langle\rangle{0pt}{}{p}{k-1}(n-p)!\\ =&n!\sum_{p\leq n}\frac{1}{p!}\genfrac\langle\rangle{0pt}{}{p}{k-1} \end{aligned}\]这里$p\leq n$是重要的。现在我们会$n^2$了。那么肯定要把欧拉数换成别的什么，怎么算欧拉数呢，简单想法是容斥，设钦点$k$个上升的方案数是$f(n,k)$，那么$\genfrac\langle\rangle{0pt}{}{n}{k}$就可以二项式反演得到。计算$f(n,k)$，考虑一个连续上升段的egf是$e^z-1$，$k-1$个上升也就是$n-k$个上升段，也就是$(e^z-1)^{n-k}$。所以答案是
\[\begin{aligned} &n!\sum_{p\leq n}\frac{1}{p!}\sum_{i\leq p}(-1)^{i-k+1}\binom{i}{k-1}p^{p-i}\\ =&n!\sum_i(-1)^{i-k+1}\binom{i}{k-1}\sum_{p=i}^n[z^p](e^z-1)^{p-i}\\ =&n!\sum_i(-1)^{i-k+1}\binom{i}{k-1}\sum_{p=0}^{n-i}[z^{p+i}](e^z-1)^p \end{aligned}\]发现右边和$k$无关，那么如果我们对每个$i$求出了这玩意，拆拆式子就可以一次卷积求出答案了。继续考虑它
\[\begin{aligned} &\sum_{p=0}^{n-i}[z^{p+i}](e^z-1)^p\\ =&\sum_{p=0}^{n-i}[z^i]\left(\frac{e^z-1}{z}\right)^p\\ =&[z^i]\frac{1-\left(\frac{e^z-1}{z}\right)^{n-i+1}}{1-\frac{e^z-1}{z}} \end{aligned}\]现在我们会$O(n^2\log n)$了，只比爆力慢一点!把分子拆开，分母和$i$无关，所以$1$可以直接求逆，但是这里分母没有常数项，所以需要先提一个$z$。考虑$\left(\frac{e^z-1}{z}\right)^{n-i+1}$一侧怎么做，好像不太能做，那么尝试加一个元$t$表示$i$的次数
\[\begin{aligned} &\sum_it^i[z^i]\frac{\left(\frac{e^z-1}{z}\right)^{n-i+1}}{1-\frac{e^z-1}{z}}\\ =&[z^0]\sum_it^iz^{-i}\frac{\left(\frac{e^z-1}{z}\right)^{n-i+1}}{1-\frac{e^z-1}{z}}\\ =&[z^0]\frac{\left(\frac{e^z-1}{z}\right)^{n+1}}{\left(1-\frac{e^z-1}{z}\right)\left(1-\frac{t}{e^z-1}\right)} \end{aligned}\]time to 拉格朗日反演。$F=e^z-1$满足方程$\ln(1+F)=z$，取$H=\frac{\left(\frac{z}{\ln(1+z)}\right)^{n+1}}{\left(1-\frac{z}{\ln(1+z)}\right)\left(1-\frac{t}{z}\right)}$，套用拉格朗日反演
\[[z^0]H(F)=[z^0]HG^\prime\frac{z}{G}=[z^0]\frac{\left(\frac{z}{\ln(1+z)}\right)^{n+1}}{\left(1-\frac{z}{\ln(1+z)}\right)\left(1-\frac{t}{z}\right)}\frac{1}{1+z}\frac{z}{\ln(1+z)}\]那么看起来是$A(z)\frac{1}{1-\frac{t}{z}}$的形式，提取$t^k$时$A$中$z$的次数就确定了，使用你的带项式板子求出$A$即可。这里$\ln(1+z)$是没有常数项的，但是由此产生的$\frac{1}{z}$会和上面的$z$消掉，所以就赢了。
新年的军队
放弃。
另一个欧拉数问题
这不是我们$\alpha$阶欧拉数吗。也就是说钦点了前$n_0$个数间的顺序对吧。那么直接dp，设$dp(i,j)$表示答案，那么有$dp(i,j)=(j+1)dp(i-1,j)+(\alpha(i-1)-(j-1))dp(i-1,j-1)$。现在我们已经会了$n\leq 2000$。
考虑$\alpha=n_0=1$，可以直接$O(n)$算欧拉数。考虑$n_0\neq 1$，我们来考虑这个dp，写其gf也就是$F_i=(zF_{i-1})^\prime-z^2F_{i-1}^\prime+z\alpha(i-1)F_{i-1}=(1+\alpha(i-1)z)F_{i-1}+z(1-z)F_{i-1}^\prime$。我们希望把这个变换凑出一个好看的形式来，试一下可以发现直接凑是凑不出来的，考虑先进行一些变换。
尝试乘一个多项式$A$，猜测有$AF_i=B(AF_{i-1})^\prime=ABF_{i-1}^\prime+A^\prime BF_{i-1}$，也就是说$B=z(1-z),\frac{A^\prime B}{A}=(1+\alpha(i-1)z)$，把$B$除过去可以看到这是$(\ln A)^\prime$，那么拿wolframalpha积一下有$A=\frac{z}{(1-z)^{\alpha(i-1)+1}}$。这个$A$为啥还跟$i$有关啊?
这个看起来可以补救，我们把和$i$有关的部分设出来，再猜一个$AB^iF_i=C(AB^{i-1}F_{i-1})^\prime=AB^{i-1}CF_{i-1}^\prime+(AB^{i-1})^\prime CF_{i-1}$，那么就有$C=z(1-z)B,(AB^{i-1})^\prime C=AB^i(1-\alpha(i-1)z)$，也就是说$z(1-z)\left(\frac{A^\prime}{A}+\frac{(i-1)B^\prime}{B}\right)=(1+\alpha(i-1)z)$，跟前面一样解得$AB^{i-1}=\frac{z}{(1-z)^{\alpha(i-1)+1}}$，那么$B=\frac{1}{(1-z)^\alpha},A=\frac{z}{(1-z)^{\alpha+1}},C=\frac{z}{(1-z)^{\alpha-1}}$。
然后这一步就比较震撼了，注意到$z\mathrm{D}$非常好，它只是给$i$次项乘上了$i$，但是$\frac{z}{(1-z)^{\alpha-1}}\mathrm{D}$就很不好。考虑把它变成$z\mathrm{D}$，我们需要使用$C$的复合逆，设它是$G$，代入可以发现它确实完成了这件事。复合$C$是$O(n\log n)$的，所以我们可以牛顿迭代$O(n\log n)$地算出$G$。
现在要计算$F_n$的一项，先快速幂算出$T_{n_0}(G)$，直接算出$T_n(G)$，然后要复合$C$，考虑拉格朗日反演直接提取$\frac{T_n}{AB^n}$，$A,B$都可以用$G(C)=z$表示。复杂度$O(n\log n)$，但是有一堆快速幂。
反射容斥
我们要计算从$(0,0)$走到$(n,m)$，每次往右上或右下走一步，不能碰到两条横线$y=a,y=b$的方案数。
根据一条禁止横线的反射容斥，我们可以计算依次碰到一组直线的方案数(也就是比如计算碰到$a$然后碰到$b$的方案数的话，在碰到$a$之前已经碰到了$b$，在碰到$b$之后又碰到了$a$之类的也都是算进去的，或者说其实我们算的是子序列)，依次反射即可。
现在我们考虑一条折线，每次碰到$a$写一个$a$，每次碰到$b$写一个$b$，得到一个串，我们希望用 这个串是否拥有某个子序列 容斥出 这个串为空。考虑计算总路径数减去碰到$a$的，减去碰到$b$的，加上依次碰到$ab$的，加上依次碰到$ba$的，减去依次碰到$aba$的，减去依次碰到$bab$的，这样的。正确性考虑首先把相邻相同的字符缩起来，因为我们这里不需要用相邻相同的字符。那么比如得到$ababa$，它包含$a,ab,aba,abab,ababa,b,ba,bab,baba$作为子序列，注意到$a$开头的个数和$b$开头的个数必然一个是奇数一个是偶数，偶数的一侧没有贡献而奇数的一侧贡献$-1$，空串贡献$1$，这就凑出来了。每次反射都会让纵坐标增大$a-b$，所以它可以表示成$O(\frac{n}{a-b})$个二项式系数的和/差。
所以也可以扩展到任意序列，比如三维的情况，有四个平行于坐标轴的禁止平面，此时我不太会构造这个容斥系数了，但是仍然可以把它递推出来。
https://blog.csdn.net/EI_Captain/article/details/105377160
想尝试gf推这个完全版啊。但是看起来我的水平不足。不过一个提示是当你看到根式的时候可以用韦达定理构造它满足的方程。
icpc22 xi’an I. Square Grid
之前vp做到了。但是他妈看错题了，需要注意这里平面是有限的不能走出去。
那么两维的走出去是独立的，也就是设$f(a,b,t)$表示在线段上走$t$步从$a$到$b$的方案数，那么答案是$\sum\limits_if(x_0,x_1,i)f(y_0,y_1,t-i)$。可以考虑类似于 王的象棋世界 的做法，但是这里并不太好用，因为是个卷积啊。
考虑直接反射容斥，相当于我们用$(n+3)\times (n+3)$的正方形铺满整个平面，在每个中得到一个反射的终点，然后按到中间的曼哈顿距离奇偶性分配容斥系数。终点在正方形中的位置有四种可能，每一种的容斥系数都是相同的。$(x_0,y_0)$到$(x_1,y_1)$的方案数，有一个经典的转化是转45度之后每次是在$x$上选$\pm 1$，$y$上也选$\pm 1$，这样相当于两维分别移动$t$次，所以答案是$\binom{t}{\frac{1}{2}(t+\vert x_1-x_0\vert)}\binom{t}{\frac{1}{2}(t+\vert y_1-y_0\vert)}$，当然拆二项式系数也能拆出这个结果。这里转了之后就变成一共八个$x,y$独立的组了。然后要对一组中所有的$x_1,y_1$求和，两个二项式系数是独立的，但是这个绝对值不是很好，但是可以注意到$t+\vert x_1-x_0\vert=\max(t+(x_1-x_0),t-(x_1-x_0))$，而因为是二项式系数，这俩其实是一样的，所以我们就是对每个$\bmod{k}$的等价类求和，这里$k=4(n+3)$是，计算$(1+z)^t\bmod{z^{2(n+3)}-1}$即可，复杂度$O(n\log n\log v+q)$。
那么这让我们想到 王的象棋世界 能不能类似做掉，看起来是可以的。