CF923E Perpetual Subtraction 做题记录

黑板上有一个整数 $x$，初始时它的值为 $[0,n]$ 中的某一个整数，其中为 $i$ 的概率是 $p_i$

每一轮你可以将 $x$ 完全随机地替换成 $[0,x]$ 中的一个数。

求 $m$ 轮后，对于每个 $i\in[0,n]$，$x=i$ 的概率。

$n \le 10^5$，$m \le 10^{18}$，答案对 $998244353$ 取模。

设 $f_m(x)$ 表示 $m$ 轮之后数为 $x$ 的答案，$F_m(x)=\sum\limits_{i=0}^n f_m(i)x^i$ 也就是 $f$ 的生成函数，那么有：

$\because f_m(x)=\sum\limits_{i=x}^n \dfrac{f_{m-1}(i)}{i+1}$

$\therefore F_m(x)=\sum\limits_{i=0}^nx^i\sum\limits_{j=i}^n\dfrac{f_{m-1}(j)}{j+1}$

$=\sum\limits_{i=0}^n \dfrac{f_{m-1}(i)}{i+1}\sum\limits_{j=0}^i x^j$

$=\sum\limits_{i=0}^n \dfrac{f_{m-1}(i)}{i+1}\dfrac{x^{i+1}-1}{x-1}$

$=\dfrac{1}{x-1}\sum\limits_{i=0}^nf_{m-1}(i)\dfrac{x^{i+1}-1}{i+1}$

注意到 $\int x^i dx=\dfrac{x^{i+1}}{i+1}$，那么：

$=\dfrac{1}{x-1}\sum\limits_{i=0}^nf_{m-1}(i)\int_1^xt^idt$

$=\dfrac{1}{x-1}\sum\limits_{i=0}^n\int_1^xf_{m-1}(i)t^idt$

$=\dfrac{1}{x-1}\int_1^xF_{m-1}(t)dt$

发现这个定积分很烦，那么考虑设 $G_m(x)=f_m(x+1)=\sum\limits_{i=0}^ng_m(i)x^i$，那么有：

$G_m(x)=\dfrac{1}{x}\int_1^{x+1}F_{m-1}(t)dt$

$=\dfrac{0}{x}\int_0^xF_{m-1}(t+1)d(t+1)$

$=\dfrac{1}{x}\int_0^xG_{m-1}(t)dt$

$=\dfrac{1}{x}\int_0^xG_{m-1}(t)dt$

$=\dfrac{1}{x}\sum\limits_{i=0}^n\dfrac{g_{m-1}(i)}{i+1}x^{i+1}$

$=\sum\limits_{i=0}^n\dfrac{g_{m-1}(i)}{i+1}x^{i}$

即 $g_m(i)=\dfrac{g_{m-1}(i)}{i+1}=\dfrac{g_1(i)}{(i+1)^{m-1}}$，接下来问题就转变为快速求出 $g_1(i)$，然后根据 $g_m(i)$ 快速求出 $f_m(i)$。

先考虑快速求出 $g_1(i)$：

$\because G_{1}(x)=F_1(x+1)$

$\therefore G_1(x)=\sum\limits_{i=0}^nf_1(i)(x+1)^i$

注意到 $f_1(i)=p_i$：

$=\sum\limits_{i=0}^n p_i(x+1)^i$

根据二项式定理展开整理：

$=\sum\limits_{i=0}^np_i\sum\limits_{j=0}^i\dbinom{i}{j}x^j$

$=\sum\limits_{i=0}^nx^j\sum\limits_{j=i}^n\dbinom{j}{i}p_j$

也就是说：

$g_1(i)=\sum\limits_{j=i}^n\dbinom{j}{i}p_j$

$=\sum\limits_{j=i}^n\dfrac{p_jj!}{i!(j-i)!}$

$=\dfrac{1}{i!}\sum\limits_{j=i}^n\dfrac{p_jj!}{(j-i)!}$

根据老套路，我们把 $p$ 反过来，设 $p'_j=p_{n-j}$，那么有：

$=\dfrac{1}{i!}\sum\limits_{j=0}^{n-i}\dfrac{p'_j(n-j)!}{(n-i-j)!}$

显然可以用卷积快速做。

接下来考虑根据 $g_m(i)$ 求出 $f_m(i)$，与上面十分类似：

$\because G_m(x)=F_m(x+1)$

$\therefore F_m(x)=\sum\limits_{i=0}^ng_m(i)(x-1)^i$

$=\sum\limits_{i=0}^ng_m(i)\sum\limits_{j=0}^i\dbinom{i}{j}x^j(-1)^{i-j}$

$=\sum\limits_{i=0}^nx^i\sum\limits_{j=i}^ng_m(j)\dbinom{j}{i}(-1)^{j-i}$

即：

$f_m(i)=\sum\limits_{j=i}^ng_m(j)\dbinom{j}{i}(-1)^{j-i}$

$=\sum\limits_{j=i}^n\dfrac{g_m(j)(-1)^{j-i}j!}{i!(j-i)!}$

$=\dfrac{1}{i!}\sum\limits_{j=i}^ng_m(j)j!\dfrac{(-1)^{j-i}}{(j-i)!}$

设 $g'_i=g_{n-i}$：

$=\dfrac{1}{i!}\sum\limits_{j=0}^{n-i}g'_m(j)(n-j)!\dfrac{(-1)^{n-i-j}}{(n-i-j)!}$

显然可以用卷积快速做。

总结一下，首先通过 $p'$ 求出 $g_1(i)$：

$g_1(i)=\dfrac{1}{i!}\sum\limits_{j=0}^{n-i}\dfrac{p'_j(n-j)!}{(n-i-j)!}$

然后根据 $g_1(i)$ 求出 $g_m(i)$：

$g_m(i)=\dfrac{g_1(i)}{(i+1)^{m-1}}$

最后根据 $g’_m(i)$ 求出 $f_m(i)$：

$f_m(i)=\dfrac{1}{i!}\sum\limits_{j=0}^{n-i}g'_m(j)(n-j)!\dfrac{(-1)^{n-i-j}}{(n-i-j)!}$