题解里面有用鞅的停时定理的做法，但我现在既不会离散时间鞅也不记得这个定理是啥了，所以搞点阳间的做法。
考虑列出操作次数的概率生成函数 \(\mathscr{P}(x)\)，也就是从初始状态开始操作 \(i\) 次后第一次达到终止状态的概率为 \([x^i]\mathscr{P}(x)\)，那么答案就是 \(\mathscr{P}'(1)\)。
注意到 \([x^i]\mathscr{P}(x)\) 有限制 \(i\) 为第一次达到终止状态，那么我们不如假设达到终止状态后继续操作。
列出另外两个 PGF，设 \([x^i]\mathscr{F}(x)\) 表示从初始状态开始，操作 \(i\) 次后到达终止状态（不一定是第一次）的概率；\([x^i]\mathscr{G}(x)\) 表示从某个终止状态开始，操作 \(i\) 次后到达某个终止状态的概率。
不难发现 \(\mathscr{G}(x)\) 中开始的终止状态是任意的，并且有 \(\mathscr{P}=\mathscr{F}\cdot \mathscr{G}^{-1}\)。
考虑 \(\mathscr{F}\) 和 \(\mathscr{G}\) 的限制，对于 \(\mathscr G\)，只要对于任意的 \(i\)，最后 \(a_i\) 步不操作 \(i\) 即可；而 \(\mathscr F\) 需要多加一个操作次数 \(\ge a_n\) 的限制。于是我们发现：
- 最后 \(a_n\) 步不能选 \(n\)。
- 最后 \(a_{n-1}\) 步不能选 \(n-1\)。
- \(\cdots\)
- 最后 \(a_2\) 步不能选 \(2\)。
即：
- 最后 \(a_2\) 步不能选 \(2,3,\cdots,a_n\)。
- 此前 \(a_3-a_2\) 步不能选 \(3,4,\cdots,a_n\)。
- \(\cdots\)
- 此前 \(a_{n}-a_{n-1}\) 步不能选 \(n\)。
那么令：
\[S_i=\prod\limits_{j=1}^{i-1}\left(\frac{j}{n}\right)^{a_{j+1}-a_j} \]\[P_i=\max\limits_{a_j\le i}j \]由于 \([x^i]\mathscr{G}(x)\) 中只能选 \(j\le P_i\) 的位置 \(j\) 操作，并且前 \(i-a_{P_i}\) 的时刻可以随便选，那么有：
\[[x^i]\mathscr{F}(x)=[i\ge n]S_n \]\[[x^i]\mathscr{G}(x)=S_{P_i}\left(\frac{P_i}{n}\right)^{i-a_{P_i}} \]于是：
\[\mathscr{F}(x)=\frac{S_nx^{a_n}}{1-x} \]\[\begin{aligned}\mathscr{G}(x)&=\frac{S_nx^{a_n}}{1-x}+\sum\limits_{i=1}^{n-1}\sum\limits_{j=a_i}^{a_{i+1}-1}S_i\left(\frac{i}{n}\right)^{j-a_i}x^j\\&=\frac{S_nx^{a_n}}{1-x}+\sum\limits_{i=1}^{n-1}S_ix^{a_i}\sum\limits_{j=0}^{a_{i+1}-a_i-1}\left(\frac{i}{n}\right)^jx^j\\&=\frac{S_nx^{a_n}}{1-x}+\sum\limits_{i=1}^{n-1}\frac{1-\left(\frac{ix}{n}\right)^{a_{i+1}-a_i}}{1-\frac{ix}{n}}\\&=\frac{S_nx^{a_n}}{1-x}+\sum\limits_{i=1}^{n-1}\frac{S_ix^{a_i}\left(1-\left(\frac{i}{n}\right)^{a_{i+1}-a_i}\cdot x^{a_{i+1}-a_i}\right)}{n-ix}\\&=\frac{S_nx^{a_n}}{1-x}+\sum\limits_{i=1}^{n-1}\frac{n(S_ix^{a_i}-S_{i+1}x^{a_{i+1}})}{n-ix}\end{aligned} \]特殊地，这里定义 \(S_1=1\)。
考虑到 \(\mathscr{P}=\mathscr{F}\cdot \mathscr{G}^{-1}\)，那么：
\[\mathscr{P}'(1)=\frac{\mathscr{F}'(1)\mathscr{G}(1)-\mathscr{F}(1)\mathscr{G'}(1)}{\mathscr{G}^2(1)} \]但是这里 \(x=1\) 时 \(\mathscr {F,G}\) 是没有意义的，于是令 \(\mathscr F,\mathscr G\) 均乘上 \(1-x\)：
\[\mathscr{F}(x)=S_nx^{a_n} \]\[\mathscr{G}(x)=S_nx^{a_n}+n\sum\limits_{i=1}^{n-1}\frac{1-x}{n-ix}(S_ix^{a_i}-S_{i+1}x^{a_{i+1}}) \]于是 \(\mathscr G(1)=\mathscr F(1)=S_n\)，令：
\[\mathscr H(x)=\sum\limits_{i=1}^{n-1}\frac{1-x}{n-ix}(S_{i+1}x^{a_{i+1}}-S_ix^{a_i}) \]\[\begin{aligned}\mathscr H'(1)&=\sum\limits_{i=1}^{n-1}\frac{(n-i)(S_{i+1}a_{i+1}-S_ia_i-S_{i+1}(a_{i+1}+1)+S_i(a_i+1))}{(n-i)^2}\\&=\sum\limits_{i=1}^{n-1}\frac{S_{i+1}-S_i}{n-i}\end{aligned} \]所以：
\[\begin{aligned}\mathscr P'(1)&=\frac{\mathscr F'(1)-\mathscr G'(1)}{S_n}\\&=\frac{n}{S_n}\cdot \mathscr{H}'(1)\\&=\frac{n}{S_n}\sum\limits_{i=1}^{n-1}\frac{S_{i+1}-S_i}{n-i}\end{aligned} \]然后就可以 \(O(n\log P)\) 做了。目前还是最优解。
标签：ix,frac,limits,mathscr,sum,nx,add,ABC270H From： https://www.cnblogs.com/Ender32k/p/17970838