YDRG#011 I 题解 / 后向微分迭代列一例

· · 算法·理论

题目来源：YDRG#011 I。

有 n 张卡片，有放回地抽取若干次，直至每张卡片都至少抽过一遍。记 X 为恰好被抽过一次的卡片个数，试求 \mathbb E[X^m],1\le m\le M。其中 n,M\le 3\times 10^5。

根据熟知变换，我们只需求出 X 的分布列即可。

假设恰好有 k 个零命角色，枚举抽卡次数 s，则

P(X=k)=\binom nk\sum_{s}k(s-1)![x^{s-1}]x^{k-1}(e^x-1-x)^{n-k}/n^s.

由 Borel 变换可得

\begin{aligned}P(X=k)&=\frac kn\binom nk\sum_{s}\frac{s!}{n^s}[x^{s}]x^{k-1}(e^{x}-1-x)^{n-k}\\&=\frac kn\binom nk\sum_{s}\frac 1{n^s}[x^{s}]\int_0^\infty(tx)^{k-1}(e^{tx}-1-tx)^{n-k}e^{-t}\text dt\\&=\frac kn\binom nk\int_0^\infty(t/n)^{k-1}(e^{t/n}-1-t/n)^{n-k}e^{-t}\text dt\\&=k\binom nk\int_0^\infty t^{k-1}(e^{t}-1-t)^{n-k}e^{-nt}\text dt.\end{aligned}

因此，若我们能求出积分

f_n(x)=\int_0^\infty (e^t-1-t+tx)^{n-1}e^{-nt}\text dt,

则 P(X=k)=n[x^{k-1}]f_n(x)。

做微分以及分部积分可知，

\begin{cases}f_n'(x)=(n-1)\int_0^\infty t(e^t-1-t+tx)^{n-2}e^{-nt}\text dt\\ f_n(x)=\frac{n-1}{n}\int_0^\infty (e^t-1+x)(e^t-1-t+tx)^{n-2}e^{-nt}\text dt\end{cases}.

由此可得微分迭代列

nxf_n=(n-1)xf_{n-1}+(x-1)^2f_n'+(x-1)f_n.

其初值为 f_1=1。

设 f_n=(n-1)!\cdot \psi^n/(x-1)\cdot g_n，则 g_n 迭代列为

nx\psi g_n=xg_{n-1}+(x-1)^2(n\psi'g_n+\psi g_n').

令 x\psi=(x-1)^2\psi'，即 \psi=(x-1)e^{x/(1-x)} 可得

g_n'=\rho g_{n-1}.

其中 \rho=x/(1-x)^3 \cdot e^{-x/(1-x)}。

做基变换换元，设 h_n=g_n\circ u，则有

h_n'=u'\rho(u)h_{n-1}.

我们希望 u'\rho(u)=x，即 (2\int\!\rho\,\text dx )\circ u=x^2，故取

u=\sqrt{2\int\!\rho\,\text dx}^{\left<-1\right>}=\sqrt{2-\frac{2}{1-x}e^{-\frac x{1-x}}}^{\left<-1\right>}.

则迭代列为 h_n'=xh_{n-1}。

由于这是个后向微分迭代列，初值 h_1 并不能帮助我们完全求出 h_n，我们还需要知道 h_1(0),h_2(0),\cdots,h_n(0)，即

h_n(0)=\frac{(-1)^{n-1}}{(n-1)!}\int_0^{\infty}(e^t-1-t)^{n-1}e^{-nt}\text dt.

注意到，若定义 a_n=\int_0^\infty (1+t)^{n-1}e^{-nt}\text dt，则

\sum_{n\ge 1}\frac{n^n}{n!}a_nx^n=-\log (1-T(x)),\quad Te^{-T}=x, h_n(0)=\frac{(-1)^{n-1}}{(n-1)!}\sum_k\binom{n-1}{k}(-1)^ka_{k+1}.

这样子 h_k(0),1\le k\le n 就能求出来了，那么 h_n 的前 n 项就是

h_n(x)=\sum_{0\le k\le (n-1)/2}\frac{h_{n-k}(0)}{2^kk!}x^{2k}+\mathcal O(x^n).

完整的算法步骤如下，时间复杂度为 \mathcal O(n\log^2 n)，瓶颈在两次复合。

  1. 求出 h_k(0), 1\le k\le n；

  2. 求出 h_n(x)=\sum_{0\le k\le (n-1)/2}\frac{h_{n-k}(0)}{2^kk!}x^{2k}；

  3. 求出 g_n=h_n\circ \sqrt{2-\frac{2}{1-x}e^{-\frac x{1-x}}}\bmod x^n；

  4. 求出 f_n(x)=(n-1)!(x-1)^{n-1}e^{nx/(1-x)}g_n(x)\bmod x^n；

  5. 分布列 P(X=k)=n[x^{k-1}]f_n(x)；

  6. 分治乘，期望 m 次方的 OGF 为 \sum_{k=1}^n\frac{P(X=k)}{1-kx}。

Remark：理论上，即便不使用 kinoshita-li 算法，本题也可以做到 \mathcal O(n\log ^2n)。这是因为第三步复合的函数可以拆解为以下复合链

\sqrt{2-\frac{2}{1-x}e^{-\frac x{1-x}}}=\sqrt{x}\circ (2-2e^x)\circ (-x+\log(1+x))\circ \frac{x}{1-x}.

其中倒数第二个函数可以用转置原理做到 \mathcal O(n\log ^2n) 复合，具体请见「KrOI2021」Feux Follets。