规定 \(\Xi:\operatorname{EGF}\rightarrow\operatorname{OGF}\)。
考虑令填满后的格子还能继续填,显然答案不变。
那么每步选每个元素的概率均为 \(\frac1n\)。
我们考虑钦定第一个格子被填满,再枚举最后一步的格子,计算概率,容易发现即为
\[(\Xi(n-1)\frac{z^{b-1}/n^b}{(b-1)!}(\sum_{i\ge a}\frac{(z/n)^i}{i!})(\sum_{i\ge b}\frac{(z/n)^i}{i!})^{n-2})(1)
\]
设 \(t=z/n\),\(u=\exp t\),那么即为
\[(\Xi_z(n-1)\frac{t^{b-1}/n}{(b-1)!}(u-\sum_{i<a}\frac{t^i}{i!})(u-\sum_{i<b}\frac{t^i}{i!})^{n-2})_z(1)
\]
从而枚举每个被填满的格子,答案即为
\[(\Xi_z(n-1)\frac{t^{b-1}}{(b-1)!}(u-\sum_{i<a}\frac{t^i}{i!})(u-\sum_{i<b}\frac{t^i}{i!})^{n-2})_z(1)
\]
容易知道
\[\Xi_zt^au^b=\frac{a!(z/n)^a}{(1-bz/n)^{a+1}}
\]
所以我们只用考虑如何快速计算
\[\frac{t^{b-1}}{(b-1)!}(u-\sum_{i<a}\frac{t^i}{i!})(u-\sum_{i<b}\frac{t^i}{i!})^{n-2}
\]
我们不妨设要计算
\[f(u,t)=(u-\sum_{i<m}\frac{t^i}{i!})^n
\]
则
\[\frac{\partial f}{\partial u}=n(u-\sum_{i<m}\frac{t^i}{i!})^{n-1}
\]
\[\frac{\partial f}{\partial t}=n(-\sum_{i<m-1}\frac{t^i}{i!})(u-\sum_{i<m}\frac{t^i}{i!})^{n-1}
\]
从而
\[nf=\frac{\partial f}{\partial t}+(u-\frac{t^{m-1}}{(m-1)!})\frac{\partial f}{\partial u}
\]
也即
\[nf_{i,j}=(j+1)f_{i,j+1}+if_{i,j}-[m-1\le j]\frac{i+1}{(m-1)!}f_{i+1,j-m+1}
\]
从而 \(j>0\) 时,我们有
\[f_{i,j}=\frac{(n-i)f_{i,j-1}+[j\ge m] (i+1)f_{i+1,j-m}/(m-1)!}j
\]
而 \(j=0\) 时显然有
\[f_{i,0}=(-1)^{n-i}\binom ni
\]
这样直接做就好了。