小孩召开法的一个尝试
Elegia
2021-09-11 15:15:48
~~三年之期已到！~~
我们考虑一个 DFA，它接受的字符是 `<` 和 `>`，每条转移边上有个边权，每个节点有个终止权值。定义一个排列的权值是把它的相邻不等关系抠出来，走过的边权值相乘，最后乘以终点的终止权值。试对 $\sum_n \left(\sum_{p\in \pi_ n} w(p)\right) x^n$ 建立生成函数。
我们以 [小孩召开法](https://loj.ac/p/6731) 为例。
> **「2019 山东一轮集训 Day3」小孩召开法** 总共有两个状态，上升（$A$）和下降（$D$），起点为 $A$，$w(A\xrightarrow{<} A) = w(D\xrightarrow{>} D)=1$，$w(A\xrightarrow{>} D)=w(D\xrightarrow{<} A)=q$，而终止权值均为 $1$。
利用概率密度扩充状态[（咋用啊？）](https://rushcheyo.blog.uoj.ac/blog/6594)，其中 $A(x,t,q), D(x,t,q)$ 中的新元 $t$ 表示末端的概率密度。立刻列出方程（下面以 $t$ 为主元）
$$
\begin{aligned}
A(t) &= 1+ x\cdot \int_0^t (A(\tau)+qD(\tau)) \,\mathrm{d} \tau\\
D(t) &= x\cdot \int_t^1(qA(\tau)+D(\tau)) \,\mathrm{d} \tau
\end{aligned}
$$
转换为微分方程组：
$$
\begin{aligned}
A' &= x\cdot (A+qD)\\
D' &= -x \cdot (qA+D)
\end{aligned}
$$
写成矩阵的形式：
$$
\begin{bmatrix}
A\\
D
\end{bmatrix}' = x \cdot
\begin{bmatrix}
1&q\\
-q&-1
\end{bmatrix} \cdot
\begin{bmatrix}
A\\
D
\end{bmatrix}
$$
把矩阵对角化，
$$
\begin{aligned}
\begin{bmatrix}
1&q\\
-q&-1
\end{bmatrix} &= P^{-1}DP\\
D &=
\begin{bmatrix}
-\sqrt{1-q^2}&\\
&\sqrt{1-q^2}
\end{bmatrix}\\
P &=
\begin{bmatrix}
\dfrac{q}{2 \sqrt{1-q^2}} & \dfrac{1}{2} \left(\dfrac{1}{\sqrt{1-q^2}}+1\right)\\
-\dfrac{q}{2 \sqrt{1-q^2}} & \dfrac{1}{2}-\dfrac{1}{2 \sqrt{1-q^2}}
\end{bmatrix}
\end{aligned}
$$
设 $\begin{bmatrix}U\\V\end{bmatrix}=P\cdot \begin{bmatrix}A\\D\end{bmatrix}$，也即解方程
$$
\begin{aligned}
U' &= -x\sqrt{1-q^2} U\\
V' &= x\sqrt{1-q^2} V
\end{aligned}
$$
解为
$$
\begin{aligned}
U &= C_1 \exp \left(-x\sqrt{1-q^2}t \right)\\
V &= C_2 \exp \left(x\sqrt{1-q^2}t \right)
\end{aligned}
$$
由 $P^{-1}\cdot \begin{bmatrix}U\\V\end{bmatrix}=\begin{bmatrix}A\\D\end{bmatrix}$，可以回带得到
$$
\begin{aligned}
A &= \frac{\sqrt{1-q^2}-1}{q} \cdot C_1 \exp \left(-x\sqrt{1-q^2}t \right) -\frac{\sqrt{1-q^2}+1}{q} \cdot C_2 \exp \left(x\sqrt{1-q^2}t \right)\\
D &= C_1 \exp \left(-x\sqrt{1-q^2}t \right) + C_2 \exp \left(x\sqrt{1-q^2}t \right)
\end{aligned}
$$
仿照新年的军队之手法，记 $\mathscr A = \int_0^1 A(t) \,\mathrm{d}t$ 以及类似的定义 $\mathscr D$。
带入 $t=0$，得到
$$
\begin{aligned}
\frac{\sqrt{1-q^2}-1}{q} \cdot C_1 -\frac{\sqrt{1-q^2}+1}{q} \cdot C_2 &= 1\\
C_1 + C_2 &= x\cdot (q\mathscr A + \mathscr D)
\end{aligned}
$$
带入 $t=1$，得到
$$
\begin{aligned}
\frac{\sqrt{1-q^2}-1}{q} \cdot C_1 \exp \left(-x\sqrt{1-q^2} \right) -\frac{\sqrt{1-q^2}+1}{q} \cdot C_2 \exp \left(x\sqrt{1-q^2} \right) &= 1 + x\cdot(\mathscr A + q\mathscr D)\\
C_1 \exp \left(-x\sqrt{1-q^2} \right) + C_2 \exp \left(x\sqrt{1-q^2} \right) &= 0
\end{aligned}
$$
解得（其中 $r = \sqrt{1-q^2}$）
$$
x(\mathscr{A} + \mathscr{D}) = \frac{\left({\mathrm{e}}^{rx}-1\right)\left(q+r+{\mathrm{e}}^{rx}+q{\mathrm{e}}^{rx}-r{\mathrm{e}}^{rx}+1\right)}{\left(q+1\right)\left(r-{\mathrm{e}}^{2rx}+r{\mathrm{e}}^{2rx}+1\right)}
$$
我们要求的就是
$$
\left[\frac{x^n}{n!} q^{K-1}\right]\frac{\left({\mathrm{e}}^{rx}-1\right)\left(q+r+{\mathrm{e}}^{rx}+q{\mathrm{e}}^{rx}-r{\mathrm{e}}^{rx}+1\right)}{\left(q+1\right)\left(r-{\mathrm{e}}^{2rx}+r{\mathrm{e}}^{2rx}+1\right)}
$$
简单整理，变成
$$
\frac{\left({\mathrm{e}}^{rx}-1\right)\left(1+{\mathrm{e}}^{rx}+\frac{r(1-{\mathrm{e}}^{rx})}{1+q}\right)}{\left(1+\frac{r-1}{r+1}{\mathrm{e}}^{2rx}\right)} \cdot \frac 1{1+r}
$$
注意 $q^2 \mid r-1$，因此下面只需展开前 $\lfloor K/2 \rfloor$ 项即可。
$$
\begin{aligned}
&\quad [x^n/n!]\frac{\left({\mathrm{e}}^{rx}-1\right)\left(1+{\mathrm{e}}^{rx}+\frac{r(1-{\mathrm{e}}^{rx})}{1+q}\right)}{\left(1+\frac{r-1}{r+1}{\mathrm{e}}^{2rx}\right)} \cdot \frac 1{1+r}\\
&= [x^n/n!] \sum_{k\ge 0} \left[\mathrm{e}^{2rx}-1 - \frac{r(\mathrm{e}^{rx}-1)^2}{1+q}\right] \cdot \frac{(r-1)^k}{(r+1)^{k+1}} \mathrm{e}^{2krx}\\
&= \sum_{k\ge 0} r^n \cdot \left[ (2k+2)^n - (2k)^n - \frac{r}{1+q} \cdot \left[(2k+2)^n - 2 (2k+1)^n + (2k)^n \right] \right] \cdot \frac{(r-1)^k}{(r+1)^{k+1}}
\end{aligned}
$$
由于幂是很难拆的，问题的关键就是计算出每个 $[q^{K-1}] r^n \frac{(r-1)^k}{(r+1)^{k+1}}$ 和 $[q^{K-1}] \frac{r^{n+1}}{1+q} \frac{(r-1)^k}{(r+1)^{k+1}}$。
> 三句话让艾鸽为我推式子 $18$ 页。
>
> 我是一个很擅长让艾鸽为我推式子的精通人性的兰讲师。
>
> 前几天我和艾鸽拿枪对峙，结束之后，我直接问了一句：“哇塞，你今天好厉害，给你个机会做道题”。他哈哈（二声）大笑，一时半会儿呢，都没有回过神来。这种啦，就是典型的直男。
>
> 然后我坐下来继续问，我们玩个问答游戏吧，他说你问我答。我说，你知道做这道题的什么时候最帅吗？他说我不知道，所以直男很无趣，普通妹妹这个时候会说，你给出第一个 observation 的时候最帅。但是我说什么，你解微分方程，处理矩阵对角化，矩阵求逆，化简公式，展开分母，处理 Algebraic GF，给最后的数列算整式递推的时候最帅。他又是一份意想不到的狂喜，接下来的全程我什么也不用干……