参考cmd 《多项式计数杂谈》，MiFaFaOvO 《A problem collection of ODE and differential technique》。
众所周知，处理生成函数的时候我们经常遇到导数和积分，常见的是三种情况 :
-
EGF平移，例如 UR3 链式反应
-
OGF凑系数，例如\(\vartheta\)算子
-
利用微积分发现性质， 例如\(O(n^2)\)的\(\exp\)
。
以下提到\(F^\prime\)及类似的式子，默认是对\(z\)求导，否则会特殊说明或者使用\(\frac{\mathrm{d}...}{\mathrm{d}...}\)的记号。
代数幂级数
称一个幂级数\(F(x)\)在\(\mathbf{K}[x]\)上是代数的，当且仅当在\(\mathbf{K}[x,y]\)上存在二元非零多项式\(G(x,y)\)，使得\(G(x,F(x))=0\)，也就是\((x,F(x))\)是\(G\)的一个根。这里\(\mathbf{K}[x]\)是系数在\(\mathbf{K}\)的多项式组成的环，\(\mathbf{K}[x,y]\)就是二元多项式组成的环。
线性齐次微分方程，微分有限和P-递归
如果一个幂级数满足一个线性齐次微分方程，那么它就是微分有限的，注意微分方程里的系数可以是多项式，而不必是常数。代数幂级数都是微分有限的。
你说什么是线性齐次微分方程?线性大家都知道，齐次就是除了\(f^{(i)}\)的项以外没有别的项了，比如不会有常数或者常多项式。
根据这个ODE容易推出它系数的递推式，这个递推式的形式一定是
\[p_0(n)f_n+p_1(n)f_{n-1}+...=0\]，其中\(p_i\)是一个多项式，这个形式被称为P-递归。事实上，一个幂级数的系数是P-递归的，当且仅当它微分有限。
关于具体如何通过ODE推出来递推式，可以看一看第一个例题，也就是 排列。
超几何与ODE
大家都知道超几何函数。《具体数学》说，我们研究的函数，95%都是超几何函数。
超几何函数有很多应用，但是今天我们只讨论它们满足的一类微分方程。
超几何函数是
\[F\left(\begin{array}{ccc|}a_1,a_2,\cdots,a_n\ \\b_1,b_2,\cdots,b_m\ \end{array}\ z\right)=\sum_{k=0}^\infty\frac{a_1^\overline{k}a_2^\overline{k}\cdots a_n^\overline{k}z^k}{b_1^\overline{k}b_2^\overline{k}\cdots b_n^\overline{k}k!}\]考虑超几何函数的导数，它是
\[\frac{\mathrm{d}}{\mathrm{d}z}F\left(\begin{array}{ccc|}a_1,\cdots,a_n\ \\b_1,\cdots,b_m\ \end{array}\ z\right)=\sum_{k=0}^\infty\frac{a_1^\overline{k+1}\cdots a_n^\overline{k+1}z^{k}}{b_1^\overline{k+1}\cdots b_n^\overline{k+1}k!}=\frac{a_1\cdots a_n}{b_1\cdots b_m}F\left(\begin{array}{ccc|}a_1+1,\cdots,a_n+1\ \\b_1+1,\cdots,b_m+1\ \end{array}\ z\right)\]我们定义\(\vartheta\)算子为\(\vartheta=z\frac{\mathrm{d}}{\mathrm{d}z}\)，也就是求导再移一位的算子。
\(\vartheta\)作用于超几何函数会有很奇妙的现象 :
\[\vartheta F\left(\begin{array}{ccc|}a_1,\cdots,a_n\ \\b_1,\cdots,b_m\ \end{array}\ z\right)=z\sum_{k=1}^\infty\frac{a_1^\overline{k}\cdots a_n^\overline{k}z^{k-1}}{b_1^\overline{k}\cdots b_n^\overline{k}(k-1)!}=\sum_{k=0}^\infty\frac{ka_1^\overline{k}\cdots a_n^\overline{k}z^k}{b_1^\overline{k}\cdots b_n^\overline{k}k!}\]好像不是很奇妙，这就是一个OGF凑系数啊?
但是凑出来的系数有妙用。让我们继续往下看 :
\[\begin{aligned} \vartheta F\left(\begin{array}{ccc|}a_1,\cdots,a_n\ \\b_1,\cdots,b_m\ \end{array}\ z\right)+a_1F\left(\begin{array}{ccc|}a_1,\cdots,a_n\ \\b_1,\cdots,b_m\ \end{array}\ z\right)&=\sum_{k=0}^\infty\frac{(k+a_1)a_1^\overline{k}\cdots a_n^\overline{k}z^k}{b_1^\overline{k}\cdots b_n^\overline{k}k!}\\ &=\sum_{k=0}^\infty\frac{a_1(a_1+1)^\overline{k}a_2^\overline{k}\cdots a_n^\overline{k}z^k}{b_1^\overline{k}\cdots b_n^\overline{k}k!}\\ &=a_1F\left(\begin{array}{ccc|}a_1+1,a_2,\cdots,a_n\ \\b_1,\cdots,b_m\ \end{array}\ z\right) \end{aligned}\]我们可以这样改一个参数!说句闲话，第一行中乘在\(F\)上的\(a_1\)也可以看做一个算子，所以我们可以把它写作\((\vartheta+a_1)F\)，这看起来简洁多了。
同理，我们也有
\[(\vartheta+b_1-1)F\left(\begin{array}{ccc|}a_1,\cdots,a_n\ \\b_1,\cdots,b_m\ \end{array}\ z\right)=(b_1-1)F\left(\begin{array}{ccc|}a_1,\cdots,a_n\ \\b_1-1,b_2,\cdots,b_m\ \end{array}\ z\right)\]这两个式子看起来很有意思。如果把上面的参数全改一遍，我们得到
\[(\vartheta+a_1)\cdots(\vartheta+a_m)F\left(\begin{array}{ccc|}a_1,\cdots,a_n\ \\b_1,\cdots,b_m\ \end{array}\ z\right)=a_1\cdots a_m F\left(\begin{array}{ccc|}a_1+1,\cdots,a_n+1\ \\b_1,\cdots,b_m\ \end{array}\ z\right)\]同理也有
\[(\vartheta+b_1-1)\cdots(\vartheta+b_m-1)F\left(\begin{array}{ccc|}a_1,\cdots,a_n\ \\b_1,\cdots,b_m\ \end{array}\ z\right)=(b_1-1)\cdots(b_m-1)F\left(\begin{array}{ccc|}a_1,\cdots,a_n\ \\b_1-1,\cdots,b_m-1\ \end{array}\ z\right)\]根据我们推的第一个式子，也就是直接求导的式子，你发现第一个是第二个的导数。
所以我们知道有微分方程
\[(\vartheta+a_1)\cdots(\vartheta+a_n)F=\frac{\mathrm{d}}{\mathrm{d}z}(\vartheta+b_1-1)\cdots(\vartheta+b_m-1)F\]，这就很好!
展开之后我们可以得到一个\(\max(n,m+1)\)阶的线性齐次微分方程。
ODE自动机/整式递推机械化
一个给出生成函数，写出ODE并解出递推式的算法。
不加证明地给出这么几个事实 :
-
常见的很多函数是微分有限的，它们的ODE很容易搞定。
-
有限多项式，\(d\)次多项式满足\(f^{(d+1)}=0\)。
-
幂函数，\(f(z)=z^\alpha\)满足\(zf^\prime=\alpha f\)。
-
超几何函数。
-
-
两个微分有限的生成函数，它们的和、积都是微分有限的，并且可以根据它们的ODE机械地推出它们和、积的ODE。
-
如果\(f\)微分有限，\(g\)是代数的，那么\(f(g)\)也是微分有限的，也可以机械地推出它的ODE。
这个算法实际表现良好。在网上可以找到这样的工具，比如EI队长的ODE自动机。
如果不能使用机器，和、积、复合的性质也生成了一大类微分有限的生成函数，我们也可以人力构造一些这样生成函数的ODE。
计数长为\(n\)，且没有两个相邻的数在数值上也相邻的排列数量。\(n\leq 10^7\)，膜\(10^9+7\)。
当然容斥。发现如果钦定\(k\)个不符合要求的间隔(就是让这些间隔两边的数在数值上相邻)，容斥系数就是\((-1)^k\)。
然后考虑这样搞的方案数，发现有些钦定的间隔可能造成了一些连续段(就是对于每个钦定的间隔，我们把它两边的东西连起来)，每一段有两种排法，不过如果长为\(1\)则只有一种。如果长是\(l\)，它对容斥系数的贡献是\((-1)^{l-1}\)(，这个情况对答案的贡献就是这些东西乘起来)。
考虑这么做 : 我们对于每一段求出它的OGF，然后直接枚举有多少段，做一个幂来拼接。这个OGF就是 :
\[T(z)=z+2\sum_{i=2}(-z)^{i-1}=z+2\frac{-z}{1+z}=\frac{z(1-z)}{1+z}\]至于拼接，我们考虑枚举段数，可以写出
\[G(z)=\sum_{i=0}i!z^i\]，这个东西含义是，对于每一段分配一个rank。\(F=G(T)\)就是答案的OGF。展开它!
\[F(z)=\sum_{i=0}i!\frac{z^i(1-z)^i}{(1+z)^i}\]然后怎么办?直接算就是\(O(n^2\log n)\)，还不够好。
\(G\)是超几何函数，\(T\)是代数的，所以我们可以构造ODE得到线性的递推式。先求导试试。
\[G^\prime (z)=\sum_{i=0}(i+1)!(i+1)z^i\]这个\((i+1)!(i+1)\)是什么啊?
仔细想想，你发现\((i+2)!=(i+1)!(i+2)\)，所以\((i+1)!(i+1)=(i+2)!-(i+1)!\)。好像又凑出来了原来的系数?
等等，\(i+1,i+2\)很毒瘤，它们会导致\(-1,-2\)次项，我们还是避开这些奇怪的东西，转而使用\(i-2,i-1\)吧。
我们做几个平移，然后减一减试一试。
\[\begin{aligned} z^2G^\prime(z)&=\sum_{i=2}(i-1)!(i-1)z^i\\ &=\sum_{i=2}(i!-(i-1)!)z^i\\ &=\sum_{i=2}i!z^i-\sum_{i=2}(i-1)!z^i\\ &=\sum_{i=2}i!z^i-\sum_{i=2}(i-1)!z^i\\ &=G(z)-1-z-(zG(z)-z)=G(z)-zG(z)-1 \end{aligned}\]看起来现在可以解ODE来得到\(G\)了，不过没有必要，因为我们只想通过ODE来递推/cy
硬代入一发\(T\)!
\[\begin{aligned} z^2G^\prime(z)&=G(z)-zG(z)-1\\ \frac{\mathrm{d}G(z)}{\mathrm{d}z}&=\frac{(1-z)G(z)-1}{z^2}\\ \frac{\mathrm{d}G(T(z))}{\mathrm{d}T(z)}&=\frac{(1-T(z))G(T(z))-1}{T(z)^2}\\ \frac{\mathrm{d}G(T(z))\cdot\mathrm{d}T(z)}{\mathrm{d}T(z)\cdot\mathrm{d}z}&=\frac{\mathrm{d}T(z)\cdot\Big((1-T(z))G(T(z))-1\Big)}{\mathrm{d}z\cdot T^2(z)}\\ F^\prime(z)&=T^\prime(z)\frac{(1-T(z))F(z)-1}{T^2(z)}\\ T^\prime(z)&=\frac{z^2+2z-1}{(1+z)^2},T^2(z)=\frac{z^2(1-z)^2}{(1+z)^2},1-T(z)=\frac{1+z^2}{1+z}\\ F^\prime(z)&=\frac{(z^2+2z-1)(1+z)^2}{(1+z)^2z^2(1-z)^2}\left(\frac{1+z^2}{1+z}F(z)-1\right)\\ &=\frac{z^2+2z-1}{z^4-2z^3+z^2}\left(\frac{1+z^2}{1+z}F(z)-1\right)\\ \end{aligned}\]先干掉分数，转成看起来可以提取系数的形式，然后直接两边取\([z^n]\) :
\[\begin{aligned} (z^2-z^3-z^4+z^5)F^\prime(z)&=(1-2z-2z^3-z^4)F(z)-1+z+3z^2+z^3\\ [z^n](z^2-z^3-z^4+z^5)F^\prime(z)&=[z^n](1-2z-2z^3-z^4)F(z)-[z^n]1+[z^n]z+[z^n]3z^2+[z^n]z^3\\ (n-1)f_{n-1}-(n-2)f_{n-2}-(n-3)f_{n-3}+(n-4)f_{n-4}&=f_n-2f_{n-1}-2f_{n-3}-f_{n-4}-[n=0]+[n=1]+3[n=2]+[n=3]\\ f_n&=(n+1)f_{n-1}-(n-2)f_{n-2}-(n-5)f_{n-3}+(n-3)f_{n-4}+[n=0]-[n=1]-3[n=2]-[n=3]\\ \end{aligned}\]这样就做到了线性复杂度。
你发现这个过程非常机械化，所以我们可以写一个弱于ODE自动机的东西来模拟，如果在场上或许不会花很长的时间。
另外这个题的\(n\)可以做到更大，比如1e9，因为我们有快速的整式递推。
顺子 加强版
来自dsq的21年省队胡策。
求有多少个长\(n\)的排列不包含长\(m\)的连续段。\(n,m\leq 5\times 10^6\)，膜\(10^9+7\)。
你发现一个顺子恰好就是上个题中的一个连续段。
考虑还是从拼接的角度理解，你发现这相当于用若干长度\(<m\)的极长顺子拼接起来的方案数。极长很困难，我们能不能容斥掉它，变成不一定极长顺子的拼接?
对于长度\(i\)，我们赋予容斥系数\(c_i\)。对于一个长\(l\)的极长顺子，考虑所有用不一定极长的顺子把它拼出来的方案。容易发现如果我们记\(c\)的OGF是\(C(z)\)，这个极长顺子的容斥系数就是\([x^l]\frac{1}{1-C(z)}\)，它应该等于\([l<m]\)，所以我们知道
\[\frac{1}{1-C(z)}=\sum_{i=0}^{m-1} z^i=\frac{1-z^{m}}{1-z}\]，可以解出
\[C(z)=\frac{z-z^{m}}{1-z^{m}}\]。它是代数的，所以把上一题的容斥系数换成这个即可。由于式子很长，建议使用机器计算。
一阶线性微分方程
都可以化成
\[f^\prime(x)=a(x)f(x)+b(x)\]的形式。然后呢?
这个东西不能直接积分，所以考虑拿个东西把右边的\(f(x)\)扔到左边来变成同一个导数，然后就可以直接积分了。容易想到使用积的求导法则。
我们两边同乘\(e^{-\int a(x)}\)。然后就得到
\[\begin{aligned} f^\prime(x)e^{-\int a(x)}-f(x)a(x)e^{-\int a(x)}&=e^{-\int a(x)}b(x)\\ \frac{\mathrm{d}(f(x)e^{-\int a(x)})}{\mathrm{d}x}&=e^{-\int a(x)}b(x)\\ f(x)e^{-\int a(x)}&=\int e^{-\int a(x)}b(x)+C\\ f(x)&=e^{\int a(x)}\int e^{-\int a(x)}b(x)+C \end{aligned}\]有根树，儿子无序，有红边和黄边。给定数集合\(A\)，计算有多少棵\(n\)个点的树，每个非叶节点满足
-
有恰好两个儿子和它连红边
-
有恰好\(k\)个儿子和它连黄边，其中\(k\)要在\(A\)中，并且这些儿子全是叶子
。\(n\leq 2\times 10^5\)，膜\(998244353\)。
显然枚举两条红边，然后剩下的都是黄边，然后这是一个卷积移一位，写成EGF就好了，注意儿子无序要除一个\(2\)。边界是单点，它肯定是叶子，注意空树为了方便看成不行。
\[\begin{aligned} f_n&=[n=1]+\frac{1}{2}\sum_{i=1}\sum_{j=1}[n-i-j-1\in A]\binom{n-1}{i}\binom{n-1-i}{j}f_if_j\\ F(z)&=\frac{1}{2}\int A(z)F^2(z)+z \end{aligned}\]现在已经可以分治FFT做到\(O(n\log^2 n)\)了!不过下面是一个\(O(n\log n)\)做法。
不定积分看起来不是很正常，我们还是换成导数吧。
\[F^\prime(z)=\frac{1}{2}A(z)F^2(z)+1\]这里有卷积，就不能直接递推了。不过这是一阶微分方程，所以应该很好解!
然而如果你拿着一个数学软件，你会发现它并不能解这个……
考虑一个倍增。类似于牛迭(多项式牛顿迭代法)，我们发现右边是一个多项式，所以设\(f(F)=\frac{1}{2}AF^2-1\)。
然后假设已经求出膜\(z^n\)意义下的答案\(F_0\)，我们在\(F_0\)处把\(f\)泰勒展开 :
\[F^\prime\equiv f(F_0)+f^\prime(F_0)(F-F_0)\pmod{z^{2n}}\]你发现\(f(F_0)\)是常多项式，所以这是一个一阶线性微分方程!
两边乘上\(e^{-\int f^\prime(F_0)}\)就可以解这个式子了，解出来我们得到\(F\equiv e^{\int f^\prime(F_0)}\int e^{-\int f^\prime(F_0)}f(F_0)+C\)。这个\(C\)怎么办?你发现它的影响总是在常数项上，而常数项应该是\(0\)，所以它完全不重要。
复杂度还是\(T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n)\)，不过常数吓人，据说比\(O(n\log^2 n/\log\log n)\)慢。
牛迭
链式反应这个题的方法可以解很大一类微分方程，见到带有卷积的微分方程可以考虑这一方法。
Gnutella Chessmaster
定义一个序列\(a_1,...,a_m\)的权值是\(\prod_{i=1}^m(a_i+i)\)。给定序列\(a\)，对于\(k=1,...,n\)，求它所有长\(k\)子序列的权值和，当然这里的子序列标号都要离散化。\(n\leq 10^5\)。
考虑一个简单dp，我们设\(f(i,j)\)表示前\(i\)个位置，所有选了\(j\)个的方案的权值和，转移是\(f(i,j)=f(i-1,j)+f(i-1,j-1)(a_i+j)\)。
既然这是 微积分和组合计数，考虑怎么用GF把它拼出来。那个系数看起来像是\(\vartheta\)……但是还是不太好，因为\(j\)和\(j-1\)对应。
我们设\(g(i,j)=f(i,i-j)\)，这样就得到\(g(i,i-j)=g(i-1,i-j-1)+g(i-1,i-j)(a_i+j)\)，也就是\(g(i,j)=g(i-1,j-1)+g(i-1,j)(a_i+i-j)\)。设\(b_i=a_i+i\)，这样就有\(g(i,j)=g(i-1,j-1)+g(i-1,j)(b_i-j)\)，这个形式就很好!
我们写出\(g(i,...)\)的OGF \(G_i(z)\)，然后就有
\[G_i=zG_{i-1}+b_iG_{i-1}-\varthetaG_{i-1}\]。这个有的移位有的不移位，看起来就只能\(O(n^2)\)了，所以我们考虑用一个跟解一阶线性微分方程类似的方法把右边第一项和第三项统一凑成\(\vartheta\)。
乘上\(e^{-z}\)即可，我们得到
\[G_ie^{-z}=\vartheta(G_{i-1}e^{-z})+b_iG_{i-1}e^{-z}\]然后提取系数!具体地，我们设\(h_{i,j}=[z^j]G_i\)，有\(h_{i,j}=h_{i-1,j}(b_i+j)\)，也就是\(h_{n,j}=h_{0,j}\prod(b_i+j)\)。后面是若干单项式乘起来，我们可以用分治FFT求出它们的积，然后做一个多点求值即可。最后卷上一个\(e^{-z}\)还原\(g(n,...)\)，然后就立刻可以得到\(f(n,...)\)。
有\(n\)个变量，一开始全是\(0\)，有上界\(a\)和阀值\(b\)。每次随机选一个没有达到上界的让它\(+1\)，如果全都\(\geq b\)了就停止，求期望有多少个达到上界。\(n,a\leq 250\)，膜\(998244353\)。
考虑一个神奇操作 : 去掉不选满的的限制，转而统计最后\(\geq a\)的期望，因为这个过程是否停止和选不选满的没有关系。
根据期望的线性性，我们可以拆开每个变量，现在只考虑\(1\)最后\(\geq a\)的概率。
这个相当于在\(1\)达到\(a\)的时候，还有一些是\(<b\)的。我们可以进行容斥。考虑如果我们钦定了\(k\)个当时\(<b\)的变量，容斥系数就是\((-1)^k\)，概率……并不是很好计算。
可以这么考虑，我们忽略掉除了钦定的这些和\(1\)之外的所有变量，问题变成每次随机一个\(0,...,k\)的数，问出现\(a\)个\(0\)的时候，其它数出现次数都\(<b\)的概率。
从拼接的角度来考虑，就是一个二项卷积。考虑一个出现次数\(<b\)的数的EGF :
\[T(z)=\sum_{i=0}^{b-1}\frac{z^i}{i!}\]那么我们就是要求所有\(T^k\)，算出这个之后剩下的部分是容易的。这个东西直接用FFT计算就可以做到\(O(n^3\log n)\)，这里认为\(n,a\)同阶。为什么不是\(O(n^2\log n)\)?因为幂有\(O(n^2)\)项，后面的东西我们还是要用到的。
怎么砍这个\(\log\)?
EGF求导就是平移，这样只差一项，然后就可以写递推式，所以可以求个导试一下?
显然\(T^\prime(z)=T(z)+\frac{z^{b-1}}{(b-1)!}\)，那么我们就知道
\[\begin{aligned} (T^k)^\prime(z)&=kT^{k-1}(z)T^\prime(z)\\ &=kT^{k-1}(z)\left(T(z)+\frac{z^{b-1}}{(b-1)!}\right) \end{aligned}\]看起来如果直接提取系数的话，这个ODE确实确定了一个递推关系。
\[\begin{aligned} (T^k)^\prime(z)&=kT^{k}(z)+\frac{z^{b-1}}{(b-1)!}kT^{k-1}(z)\\ [z^n](T^k)^\prime(z)&=[z^n]kT^{k}(z)+[z^n]\frac{z^{b-1}}{(b-1)!}kT^{k-1}(z)\\ [z^{n+1}]T^k(z)&=k[z^n]T^{k}(z)+\frac{1}{(b-1)!}[z^{n-b+1}]kT^{k-1}(z) \end{aligned}\]这就结束了。
给\(d\)，求在\([1,d]\)中有序地选\(n\)个数，使得其中可以选出至少\(m\)个不交的对，每一对数值相等的方案数。\(d\leq 10^5,n,m\leq 10^9\)，膜\(998244353\)。
考虑一个方案可行，我们设颜色\(c\)出现\(cnt_c\)次，那么可行当且仅当\(\sum_c\lfloor\frac{cnt_c}{2}\rfloor\geq m\)。
然后就很简单了!这看起来就很像要对奇偶性分类讨论。你发现如果奇数非常多，那么就会在下取整这里产生很大的”损耗”。具体地，如果奇数个数超过了\(n-2m\)，我们就会损失掉至少\(n-2m\)，这样剩下的就不够\(m\)了。问题变成求奇数个的颜色个数不超过\(k=\min(d,n-2m)\)的方案数。
从拼接的角度来考虑。写出一个奇数的EGF，它就是\(\frac{e^z-e^{-z}}{2}\)，容易直接展开验证。一个偶数的EGF则是\(\frac{e^z+e^{-z}}{2}\)。
于是我们就是要求
\[\sum_{i=0}^k\binom{d}{i}n![z^n]\left(\frac{e^z-e^{-z}}{2}\right)^i\left(\frac{e^z+e^{-z}}{2}\right)^{d-i}\]。这个不是很好看，可以提出来各种东西
\[\frac{n!}{2^d}[z^n]\sum_{i=0}^k\binom{d}{i}\left(e^z-e^{-z}\right)^i\left(e^z+e^{-z}\right)^{d-i}\]，然后可以写成一个生成函数
\[F(z)=\sum_{i=0}^k\binom{d}{i}\left(e^z-e^{-z}\right)^i\left(e^z+e^{-z}\right)^{d-i}\]。如何快速计算?首先你发现\(z\)全是以\(e^z\)或者\(e^{-z}\)形式出现的，我们考虑另一个东西 :
\[\sum_{i=0}^k\binom{d}{i}\left(z-\frac{1}{z}\right)^i\left(z+\frac{1}{z}\right)^{d-i}\]这个还不是很好看，因为有一个\(-1\)次方，不过我们还是可以提一下
\[\sum_{i=0}^k\binom{d}{i}\left(z^2-1\right)^i\left(z^2+1\right)^{d-i}\]，然后你发现关于\(z\)的又只剩下\(z^2\)了，我们可以再进行一次换元
\[G(z)=\sum_{i=0}^k\binom{d}{i}\left(z-1\right)^i\left(z+1\right)^{d-i}\]，这就很好!原来的答案是
\[F(z)=\frac{1}{e^{dz}}G(e^{2z})\]这样只要求出\(G\)，算\(F\)就是普及组内容了。
直接求导!
\[G^\prime(z)=\sum_{i=1}^{k}\binom{d}{i}\left(i(z-1)^{i-1}(z+1)^{d-i}+(z-1)^i(d-i)(z+1)^{d-i-1}\right)\]这个怎么跟\(G\)联系起来呢……试一试可以发现有这么一个奇怪的式子 :
\[dG-zG^\prime=d\binom{d-1}{k}(z-1)^k(z+1)^{d-k-1}\]右边现在是经典式子 :
\[f(z)=(1+z)^a(1-z)^b\rightarrow f^\prime(z)=\frac{af(z)}{1+z}+\frac{bf(z)}{1-z}\]所以我们可以递推出\(dG-zG^\prime\)了，而这个东西又给出了一个递推式，所以我们又可以求出\(G\)了，所以就做完了。
现在瓶颈在求幂。不过我们可以通过线性逆元和线性筛幂做到接近线性。
中国象棋
有一个\(n\times m\)的棋盘，现在要往上摆炮，要求任意两个炮不能互相攻击，求方案数膜\(998244353\)，可以加强到\(10^9+7\)。\(n,m\leq 5\times 10^4\)。
等价于每行每列都不超过两个炮。
考虑对每行每列建一个点，这样一个炮就相当于连在它的行列之间的一条边。问题等价于计数左右分别\(n,m\)个点的二分图，其中每个点度数不超过\(2\)，当然还要没有重边。
你发现这个度数限制非常经典，这个二分图应该是若干不交的链和环的并。从拼接的角度考虑，我们可以写出偶环，偶链和奇链的二元EGF(单点视为奇链) :
\[\begin{aligned} F&=\sum_{i=2}\frac{x^iy^i}{2i}\\ G&=\sum_{i=1}x^iy^i\\ H&=\frac{1}{2}\sum_{i=1}\left(x^iy^{i+1}+x^{i+1}y^i\right)+x+y \end{aligned}\]答案就是\(n!m![x^ny^m]e^{F+G+H}\)了。
二元GF确实不好办，所以我们考虑转成一元的。偶环和偶链中每一项\(x,y\)次数都是相同的，所以可以直接改写成一个\(z\)。奇链就不能这么处理。不过你发现如果我们假设\(n\geq m\)，那么因为奇链在两边的点数刚好差\(1\)，出发于左边的奇链必然比出发于右边的奇链多\(n-m\)条，也就是说我们枚举出发于右边的奇链数量的话，左边的数量已经确定了，所以可以用一元GF直接描述这件事。
可以写出新的EGF :
\[\begin{aligned} F&=\sum_{i=2}\frac{z^i}{2i}\\ G&=\sum_{i=1}z^i\\ H&=z+\frac{1}{2}\sum_{i=2}z^i \end{aligned}\]然后答案现在是\(n!m![z^n]e^{F+G}\sum_{i=0}^n\frac{H^iH^{n-m+i}}{z^ii!(n-m+i)!}\)。
我们提一个\(H^{n-m}\)出来，然后设\(P(z)=\sum_{i=0}\frac{z^i}{i!(n-m+i)!},Q(z)=\frac{H^2(z)}{z}\)，那么上面那个困难的式子就变成了\(P(Q)\)。
你发现\(P\)是超几何函数乘常数，\(H\)是代数的(可以直接解封闭形式)，所以\(Q\)也是代数的，所以它们的复合还是微分有限的。使用ODE自动机即可。
剩下的部分呢?实际上\(F,G\)也都是代数的，\(e^z\)是超几何函数，然后你就可以使用ODE自动机解决了。
我们也有手算的方法。考虑\(P\)的微分方程很简单，问题是怎么求\(P(Q)\)的微分方程。你发现直接代入\(Q\)可以得到一个微分方程，但是里面全是\(P^\prime(Q)\)或者\(P^{\prime\prime}(Q)\)这样的东西，而我们想要的是\((P(Q))^\prime\)这样的。可以使用链式法则，它建立了复合的导数和导数的复合之间的关系，所以我们可以用\((P(Q))^\prime\)表示\(P^\prime(Q)\)，然后代回去就得到关于\(P(Q)\)的ODE了。然后使用FFT就一个\(\log\)了。
分治FFT
你发现上面的最后一段可以用来求微分有限幂级数\(F\)复合任意幂级数\(G\)。我们构造\(F\)的微分方程，然后就可以得到\(F(G)\)的微分方程，它必然也是线性齐次的，不过其中可能有卷积，可以用分治FFT求解。
结合牛迭可以做到\(O(n\log^2 n)\)解任意微分有限幂级数的复合逆。这个怎么做?
直接牛迭。要求\(G\)的复合逆\(F\)，我们直接设就是设\(f(F)=G(F)-z\)，求导显然很简单，主要问题就是要算微分有限幂级数复合任意幂级数，这就是上面的东西了。看起来常数并不小。
Simple Permutations
定义一个排列是一个简单排列(simple permutation)，当且仅当它不存在非平凡的连续段，连续段就是值域连续区间，非平凡指的是长度不为\(0,1,n\)。求有多少长\(n\)的简单排列。\(n\leq 5\times 10^4\)，膜\(998244353\)。
设答案是\(s_n\)。
我们看起来要从连续段出发。定义一个排列的分解是一种把它划分成若干连续段的方案，比如\(67183524\)可以分解成\(67,1,8,3524\)，可以进一步标准化变成\(12,1,1,2413\)。一个简单排列应该只有两种平凡的分解，也就是分成一个和分成\(n\)个。
你发现，如果我们想把一个排列分成尽量少的连续段(当然不要长为\(n\)的)，从全是长为\(1\)的连续段开始合并，最后一定会不能继续合并，此时把所有连续段拿出来排序(排列中两个连续段一定可比，这里的比较指的是它们整体的相对大小)，得到的排名数组应该是一个简单排列，换句话说这些连续段的大小关系等于一个简单排列中的大小关系。这怎么证明?这是显然的，因为如果不简单，那么说明还可以继续合并连续段。
这可能给出了一种双射!
与分解对应地，我们定义一个长\(m\)的排列\(\sigma\)的膨胀\(\sigma[\alpha_1,\alpha_2,...,\alpha_m]\)，其中\(\alpha_i\)也都是排列，为把\(\sigma\)中的元素从小到大替换成对应位置上的\(\alpha\)，当然后替换进来的需要整体加上偏移量。例如\(3142[12,1,1,2413]=67183524\)。这里面的\(\sigma\)就是我们上面说的连续段们的排名数组。
接下来做一些可能不显然的事情。定义一个排列是正不可分的，当且仅当它不能由\(12\)膨胀得来，负不可分则是不能由\(21\)膨胀得来。定义\(i_n\)是长\(n\)的正不可分排列数量，负不可分排列显然也是这么多。
然后我们尝试证明下面的定理 :
定理 对于任意长度不为\(1\)的排列\(\pi\)，都存在恰好一个长度不为\(1\)的简单排列\(\sigma\)，膨胀之后可以得到\(\pi\)。
如果\(\sigma\)的长度\(>2\)，那么\(\alpha_i\)们也是唯一的，\(=2\)时则有两种方案。如果\(\sigma=12\)，并且我们要求\(\alpha_1\)是正不可分的，那么\(\alpha_1,\alpha_2\)也是唯一的了；\(\sigma=21\)中则是负不可分。
证明
考虑如果\(\pi\)中所有非平凡极长连续段都是不交的。我们直接取这些连续段就得到了唯一的分解方式。怎么证明这样得到的\(\sigma\)是简单的?既然不能继续合并连续段，它必然是简单的。
然后考虑\(\pi\)中存在两个不同的非平凡极长连续段\(A,B\)，并且它们的交非空的情况。
你发现既然它们的交非空，那么它们的并一定也是值域连续的，所以它们的并一定是平凡的\([1,n]\)，不然就不极长了。
然后考虑如果从其中一个连续段中挖掉两个连续段的交，得到的应该还是连续段，于是我们知道\(\pi=\sigma[\alpha,\beta]\)，其中\(\sigma=12\)或者\(21\)是唯一的，但是\(\alpha,\beta\)的方案数是不确定的。这就很不好，因为它不是双射了。
不过如果我们考虑所有分成\(\sigma[\alpha,\beta]\)的方式，其中有唯一一个是满足\(\alpha\)最短的，我们钦定这个就是我们想要的。如果\(\sigma=12\)，这个最短的\(\alpha\)显然是正不可分的，否则把它分掉就得到更短的\(\alpha\)；\(\sigma=21\)时则是负不可分。这就证完了。
现在我们确实利用这个结论建立了一个\((\sigma,\alpha_1,...,\alpha_m)\)到任意排列的双射，其中\(\sigma\)是长为\(m\geq 2\)的简单排列，不过这里长为\(1,2\)的\(\sigma\)是特殊的，它们要求\(\alpha_1\)是正或者负不可分的。
考虑\(n!,i_n,s_n(n\geq 1)\)的生成函数\(F,I,S\)，其中\(S\)只考虑\(n\geq 4\)的项，可以得到
\[F=z+2IF+S(F)\]，其中\(z\)是因为\(1\)并不能被这么表示。这个看起来很好。
要解出\(S\)我们还需要消掉\(I\)，不过显然应该可以搞出这么一个关于\(I\)的方程。考虑要生成全部排列和要生成正不可分排列的区别，就在于\(\sigma\)不能取\(12\)了，所以就是上面式子中间那个系数\(2\)变成\(1\)了，我们得到
\[I=z+IF+S(F)\]，然后进行一些操作就可以解出
\[S(F)=\frac{F-F^2}{1+F}-z\]。接下来是经典做法 : 换元，把\(z\)换成\(F^{\langle -1\rangle}\)(\(F\)的复合逆)，这样就把\(S(F(z))\)变成\(S(z)\)了
\[S(z)=\frac{z-z^2}{1+z}-F^{\langle -1\rangle}\]。前面那个东西容易计算，它是\(z(1-z)\frac{1}{1+z}\)，分别是平移、邻项差和\((-1)^n\)，于是我们得到\(2(-1)^{n+1}\)。
所以就是要算复合逆了。你发现\(F\)是超几何函数减去常数项\(1\)，容易得到它的ODE，然后利用上面的技术就可以解决这个问题。