P4831 题解与「中国象棋」一题的扩展

· · 题解

原题是不限制炮数，这里给生成函数增加一元以计量炮数，大概算是扩展吧。（而且要求原题只需令计量炮数的元为 1 即可）

沿着 yhx 奆佬的思路，我们直接设要求摆恰好 k 个炮的情况。此题中 k=2n 的情况较为简单，这里我们考虑更普遍的情况。

首先来复读一下组合推导，一样是用二分图建模，转化为计数：左边 n 个点，右边 m 个点，连恰好 k 条边，图中只有链与环的有标号二分图。

  1. 还是先来考虑环，记 n!m![x^ny^mz^k] R 为对环的计数。由于环上连接的点必须是二分图上左右交替，点数应当相同。又由于是环排列，总数要除以 2n，得到

    R=\sum_{n=2}^\infty \frac{(n!)^2}{2n}\times \frac{x^ny^nz^{2n}}{(n!)^2} =\frac 12\sum_{n=2}^\infty \frac{(xyz^2)^n}{n}=-\frac 12(\ln(1-xyz^2)+xyz^2)

  2. 对于有偶数个点的链，两边包含的点数也是相同的，仿照刚才的思路直接列出

    C_e=\sum_{n=1}^\infty (n!)^2 \times \frac{x^ny^nz^{{2n-1}}}{(n!)^2}=\frac{xyz}{1-xyz^2}

  3. 有奇数个点的链的首尾都在一侧节点上，还按照刚才的做法得到左边 n 个，右边 n+1 个点的链会有 n!(n+1)! 个 —— 但链是不分正反的，首尾相同时无法区分，所以对 n\geq 1 时要除 2。

C_o=x+y+\frac 12\sum_{n=1}^\infty n!(n+1)!z^{2n} \frac{x^ny^{n+1}+x^{n+1}y^n}{n!(n+1)!} =(x+y)\frac{2-xyz^2}{2-2xyz^2}

然后答案的生成函数就是 \exp(R+C_e+C_o)。这个三元生成函数看着就让人头大，以下内容基本口胡，如有错误请毫不留情地指出。

根据某个技巧的扩展，\exp R 的系数都是形如 x^iy^iz^{2i} 的，我们只需要把 \exp(C_e+C_o) 中形如 x^{n-i}y^{m-i}z^{k-2i} 的系数提出来即可。
设 d_1=m-n，d_2=2n-k，要提的系数可改写为 x^iy^{i+d_1}z^{2i-d_2}。将 \exp(C_e+C_o) 展开得到

\sum_{i=0}^\infty \frac{1}{(1-xyz^2)^ii!}\sum_{j=0}^i \binom ij (xyz)^{i-j} (x+y)^j(2-xyz^2)^j2^{-j}

注意到「乘只含 xyz^2 的项」这个操作，并不改变其中的项「是否属于我们要提取的」这一性质。

令 j=2t+d_1，则从 (x+y)^j 中即可提取出 x^ty^{t+d_1} 的项，是我们要的一部分；(xyz)^{i-j} 中提供的 x^{i-j}y^{i-j} 项也不影响 y,x 指数差为 d_1，故只需保证 x 指数的二倍减去 z 的指数为 d_2，也就是 2(t+i-j)-(i-j)=d_2，化简得 i=d_2+d_1。

于是把我们要提取的系数拿出来，就组成了下式。为方便表示，记 c=d_1+d_2。

\frac{1}{(1-xyz^2)^cc!}\sum_{t\geq0} \binom c{2t+d_1}\binom{2t+d_1}{t}x^ty^{t+d_1}(xyz)^{c-2t-d_1}(1-xyz^2/2)^{2t+d_1}

看起来还是很复杂，但做换元 u=xyz^2 就能化简为

\frac{x^{d_2}y^cz^{d_2}}{(1-u)^cc!}\sum_{t\geq 0} \binom{c}{2t+d_1} \binom{2t+d_1}{t}u^{-t}(1-u/2)^{2t+d_1}

这个 u 的负指数看起来很诡异，但把它扔到 mma 里算出来确实是对的，，现在可以设

F(u) = \frac{(1-u/2)^{d_1}}{(1-u)^c}\sum_{t\geq 0 } \binom{c}{2t+d_1} \binom{2t+d_1}{t} u^{-t}(1-u+u^2/4)^{t}

前面这个分式显然微分有限，先考虑后面：

G(u) = \sum_{t\geq 0 } \binom{c}{2t+d_1} \binom{2t+d_1}{t} (u^{-1}-1+u/4)^{t}

这是一个超几何级数和一个有理分式的复合，G(u) 就是微分有限的，于是 F(u) 是微分有限的。

现在倒回来看 \exp R，有

\mathcal R(u)=\exp R = \frac{\text e^{-u/2}}{\sqrt{1-u}}

显然 \mathcal R(u) 也是微分有限的，最终答案也微分有限，可以做到 \Theta(n) 或 \Theta(\sqrt n \log n)。

ps：我知道你想要什么。最终答案为

n!m^{\underline{k-n}}[u^{k-n}] \left( \frac{\text e^{-u/2}(1-u/2)^{d_1}}{(1-u)^{c+1/2}} \sum_{t\geq 0} \binom{c}{2t+d_1}\binom{2t+d_1}{t}(u^{-1}-1+u/4)^t\right)

其实整篇题解都只是依葫芦画瓢，最后再膜一发奆佬 yhx。