ABC270H add 1
Arghariza
·
·
个人记录
题解里面有用鞅的停时定理的做法，但我现在既不会离散时间鞅也不记得这个定理是啥了，所以搞点阳间的做法。
考虑列出操作次数的概率生成函数 \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) 做了。目前还是最优解。