5e10的小石子
感谢qiu老师的长期连载系列让我入门整式递推/bx/bx
part1 基础推导
首先观察到我们每一行必须有 \(2\) 个数，然后每一列之多两个数。
我们把同一行的连边，同一列的连边。
不难发现每个点的度数 \(\le2\) 连出的一定就是环或者链。
那么考虑实际上他本质上是一个二元egf（需要同时分配行列）。
考虑一个 \(n\times n\) 矩阵嵌入环的方案数，\(\frac{1}{2}(n-1)!n!\) （我们钦定 \(1\) 为起点，行往下的排列，以及列随意排列， 最终除掉正反两种情况）。
接下来考虑链的情况，\(n\times(n+1)\) 矩阵嵌入链的方案数，\(\frac{1}{2}n!(n+1)!\)。（\(n!\) 枚举起点的行列，然后枚举列的置换。）
其实我们可以直接写 \(\frac{[x^n][y^m]}{n!m!}\) 状物，可是我太菜了，不会推多元GF，所以写一个看起来没有二元GF的。
我们可以直接枚举链的条数，这样就知道具体情况了。此时这和下面的 \(s=xy\) 换元本质相同。也可以发现多元GF推到会更加简单。
addition:二元EGF \[ \begin{aligned} \hat F(x,y)&=\frac{1}{2}(\ln(1-xy)-xy)\\ \hat G(x,y)&=\frac{1}{2}xy^2\frac{1}{1-xy}\\ \hat P(x,y)&=y\\ \hat H(x,y)&=\exp \hat F(x,y)\times \exp \hat G(x,y)\times \exp \hat P(x,y)\\ \hat H(s,y)&=\exp (\frac{1}{2}(\ln(1-s)-s)+\frac{1}{2}sy\frac{1}{1-s}+y)\\ &=\exp (\frac{1}{2}(\ln(1-s)-s))\exp((\frac{s}{2-2s}+1)y)\\ \end{aligned} \]
y实际上已经独立了，多元生成函数我们在我们需要提取某一元的时候，把其他元要当成常量。
\[ \begin{aligned} \exp((\frac{s}{2-2s}+1)y)\\ [x^m]\exp(ay)=\frac{1}{m!}a^m \end{aligned} \]
\[ \begin{aligned} \hat H(s,y)&=\exp (\frac{1}{2}(\ln(1-s)-s))\exp((\frac{s}{2-2s}+1)y)\\ [x^n][y^m]\hat H(x,y)&=[s^n][y^{m-n}]\hat H(s,y)=\frac{[s^n]}{(m-n)!}\exp(\frac{1}{2}(\ln(1-s)-s))\times(\frac{s}{2-2s}+1)^{n-m}\\ &=\frac{[s^n]}{(m-n)!}(1-s)^{1/2}\times e^{-1/2s}\times(\frac{s}{2-2s}+1)^{n-m}\\ \end{aligned} \]
怎么做捏？
接下来要介绍一下 d-finite，微分有限函数。
我们称满足以下的的函数成为 d-finite的。
若存在 \(r\)，以及 \(r+1\) 个多项式\(a_0,\cdots a_r\)使得 \(\sum_{i=0}^rF^{(i)}(x)a_i(x)=C(x)\) 我们称其满足一个线性微分方程组，\(r\) 被称为 阶。
若 \(C(x)=0\) 我们称其满足一个 齐次线性微分方程组。同时他也是微分有限的。
首先显然多项式全部微分有限。
若 \(F(x),G(x)\) 都微分有限，那么 \(aF(x)+bG(x),F(x)G(x)\) 也同样微分有限。
证明嘛，暂时不太会。
如果 \(F(x)\) 微分有限，\(G(x)\) 是代数函数，那么 \(F(G(x))\) 微分有限。（代数函数说的是只包含加减乘除，乘方开方的函数）。
然后一些简单的形如 幂函数 \(x^a\) \(a\cdot x^a-x\cdot ax^{a-1}=0\),指数函数 \(a^x=e^{\ln bx},\ln b e^{\ln b x}-\ln be^{\ln b x}=0\)
d-finite 复合。
低阶 d-finite 的 \(F,G\)，我们要在 \(\tilde O(n)\) 求 \(F(G(x))\)。
回来看一下方程： \[ \begin{aligned} \sum_{i=0}^r F^{(i)}(x)a_i(x)&=0\\ \sum_{i=0}^r F^{(i)}(G(x))a(G(x))&=0\\ F(G(x))^{(n)}&=\sum_{i=0}^n\binom{n}{i}G^{(i)}(x)F^{(n-i)}(G(x)) \end{aligned} \]
咕掉了。有缘再更。
具体的 \((1-s)^{-1/2}\times e^{-1/2}\) 这个可以求导对比系数。\((\frac{2-s}{2-2s})^m\) 可以求导对比系数。
就完事了。我不知道有什么拓展。