小孩召开法的一个尝试

· · 个人记录

三年之期已到！

我们考虑一个 DFA，它接受的字符是 < 和 >，每条转移边上有个边权，每个节点有个终止权值。定义一个排列的权值是把它的相邻不等关系抠出来，走过的边权值相乘，最后乘以终点的终止权值。试对 \sum_n \left(\sum_{p\in \pi_ n} w(p)\right) x^n 建立生成函数。

我们以 小孩召开法 为例。

「2019 山东一轮集训 Day3」小孩召开法 总共有两个状态，上升（A）和下降（D），起点为 A，w(A\xrightarrow{<} A) = w(D\xrightarrow{>} D)=1，w(A\xrightarrow{>} D)=w(D\xrightarrow{<} A)=q，而终止权值均为 1。

利用概率密度扩充状态（咋用啊？），其中 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，给最后的数列算整式递推的时候最帅。他又是一份意想不到的狂喜，接下来的全程我什么也不用干……