题解 | #抽奖#

F 抽奖

考虑枚举每次抽到奖品需要的次数，恰好抽 $nn$ 次后中奖的概率就是 $(1-q{)}^{n-1}q(1-q)^\{n-1\}q$，就有计算式：

$E(x^k)={\displaystyle \frac{q^m}{(1-q{)}^m}}{\displaystyle \sum _{n_1=1}^{\mathrm{\infty }}\sum _{n_2=1}^{\mathrm{\infty }}\cdots \sum _{n_m=1}^{\mathrm{\infty }}{\left(\sum _{i=1}^m{n}_i\right)}^k\prod _{j=1}^m(1-q{)}^{n_j}}E(x^k)\; =\; \backslash dfrac\{q^m\}\{(1-q)^m\}\backslash displaystyle\backslash sum\_\{n\_1=1\}^\{\backslash infty\}\backslash sum\_\{n\_2=1\}^\backslash infty\; \backslash cdots\backslash sum\_\{n\_m=1\}^\{\backslash infty\}\backslash left(\; \backslash sum\_\{i=1\}^m\; n\_i\backslash right)^k\backslash prod\_\{j=1\}^m(1-q)^\{n\_j\}$

根据 $i^k=k![x^k]{\text{e}}^{ix}i^k=k![x^k]\backslash text\; e^\{ix\}$，答案就可以写为

$E(x^k)={\displaystyle \frac{q^m}{(1-q{)}^m}}\left[{\displaystyle \frac{x^k}{k!}}\right]{\displaystyle \sum _{n_1=1}^{\mathrm{\infty }}{\text{e}}^{n_{1}x}(1-q{)}^{n_1}\sum _{n_2=1}^{\mathrm{\infty }}{\text{e}}^{n_{2}x}(1-q{)}^{n_2}\cdots \sum _{n_m=1}^{\mathrm{\infty }}{\text{e}}^{n_{m}x}(1-q{)}^{n_m}}E(x^k)=\; \backslash dfrac\{q^m\}\{(1-q)^m\}\backslash left[\; \backslash dfrac\{x^k\}\{k!\}\backslash right]\backslash displaystyle\backslash sum\_\{n\_1=1\}^\{\backslash infty\}\backslash text\; e^\{n\_1x\}(1-q)^\{n\_1\}\backslash sum\_\{n\_2=1\}^\backslash infty\; \backslash text\; e^\{n\_2x\}(1-q)^\{n\_2\}\backslash cdots\backslash sum\_\{n\_m=1\}^\{\backslash infty\}\; \backslash text\; e^\{n\_mx\}(1-q)^\{n\_m\}$

注意到这样各个和式之间就不相关了，可以直接写为各和式的乘积：

$E(x^k)={\displaystyle \frac{q^m}{(1-q{)}^m}}\left[{\displaystyle \frac{x^k}{k!}}\right]{({\displaystyle \frac{1}{1-(1-q){\text{e}}^x}}-1)}^{m}E(x^k)\; =\; \backslash dfrac\{q^m\}\{(1-q)^m\}\backslash left[\; \backslash dfrac\{x^k\}\{k!\}\backslash right]\backslash left(\; \backslash dfrac\{1\}\{1-(1-q)\backslash text\; e^x\}-1\backslash right)^m$

设 $r=1-qr=1-q$，那么现在的问题就变为提取 $q^m{\text{e}}^{mx}(1-r{\text{e}}^x{)}^{-m}q^m\backslash text\; e^\{mx\}(1-r\backslash text\; e^x)^\{-m\}$ 的 $x^{k}x^k$ 系数，使用 FFT 就可以做到 $\mathrm{\Theta }(k\log k)\backslash Theta(k\; \backslash log\; k)$ 的时间复杂度，但这显然是不够的。

根据 EI 总结的一套方法，设 $F(x)=(x+1{)}^m(1-r(x+1){)}^{-m}F(x)=(x+1)^m(1-r(x+1))^\{-m\}$，所求即 $q^m[x^k]F({\text{e}}^x-1)q^m[x^k]F(\backslash text\; e^x-1)$。

由于 ${\text{e}}^x-1\backslash text\; e^x-1$ 没有常数项，所以次数高于 $x^{k}x^k$ 的项对于答案没有贡献，我们只需知道 $\mathcal{F}(x)=F(x)\mathrm{m}\mathrm{o}\mathrm{d}{x}^{k+1}\backslash mathcal\; F(x)\; =\; F(x)\; \backslash bmod\; x^\{k+1\}$，然后求 $[x^k]\mathcal{F}({\text{e}}^x-1)[x^k]\backslash mathcal\; F(\backslash text\; e^x-1)$ 即可。

直接这样算并没有优化复杂度，但 $\mathcal{F}(x)\backslash mathcal\; F(x)$ 的系数是可整式递推的，设 $\mathcal{G}(x)=\mathcal{F}(x-1)\backslash mathcal\; G(x)\; =\; \backslash mathcal\; F(x-1)$，则 $\mathcal{G}(x)\backslash mathcal\; G(x)$ 也是可整式递推的，其前 $kk$ 项系数可以 $\mathrm{\Theta }(k)\backslash Theta(k)$ 计算，再配合线性筛就可以计算出 $[x^k]\mathcal{G}({\text{e}}^x)[x^k]\backslash mathcal\; G(\backslash text\; e^x)$。

具体来讲，求导一下可以得到 $F(x)F(x)$ 的 ODE：

$(1+x)(q-rx)F^{\mathrm{\prime }}(x)-m(r+q)F(x)=0(1+x)(q-rx)F\text{'}(x)\; -\; m(r+q)F(x)\; =\; 0$

提取 $x^{n-1}x^\{n-1\}$ 系数：

$nq{F}_n+(q-r)(n-1)F_{n-1}-r(n-2)F_{n-2}-m(r+q)F_{n-1}=0nqF\_n+(q-r)(n-1)F\_\{n-1\}-r(n-2)F\_\{n-2\}-m(r+q)F\_\{n-1\}=0$

设 $f_n=[x^n]\mathcal{F}(x)f\_n=[x^n]\backslash mathcal\; F(x)$，$u=-(k+1)q{F}_{k+1}u=-(k+1)qF\_\{k+1\}$，$v=-rk{F}_{k}v=-rkF\_k$，就有

$nq{f}_n+(q-r)(n-1)f_{n-1}-r(n-2)f_{n-2}-m(r+q)f_{n-1}=[n=k+1]u+[n=k+2]vnqf\_n+(q-r)(n-1)f\_\{n-1\}-r(n-2)f\_\{n-2\}-m(r+q)f\_\{n-1\}=[n=k+1]u+[n=k+2]v$

写做 ODE 就是

$(1+x)(q-rx){\mathcal{F}}^{\mathrm{\prime }}(x)-m(r+q)\mathcal{F}(x)=u{x}^k+v{x}^{k+1}(1+x)(q-rx)\backslash mathcal\; F\text{'}(x)-m(r+q)\backslash mathcal\; F(x)\; =\; ux^k+vx^\{k+1\}$

做代换 $x=t-1x=t-1$，得到 $\mathcal{G}(t)\backslash mathcal\; G(t)$ 的 ODE：

$t(q-r(t-1)){\mathcal{G}}^{\mathrm{\prime }}(t)-m(r+q)\mathcal{G}(t)=u(t-1{)}^k+v(t-1{)}^{k+1}t(q-r(t-1))\backslash mathcal\; G\text{'}(t)-m(r+q)\backslash mathcal\; G(t)\; =\; u(t-1)^k+v(t-1)^\{k+1\}$

直接提取系数就能得到递推式，这里就不赘述了。
总时间复杂度 $\mathrm{\Theta }(k)\backslash Theta(k)$。