【题解】Luogu-P4705 玩游戏

Luogu-P4705 玩游戏

给定长度分别为 $n,m$ 的序列 $a,b$，随机取两个下标 $x,y$，定义其 $k$ 次价值为 $(a_x+b_y)^k$。
求对于 $i\in[1,t]$，一次游戏的 $i$ 次价值的期望分别是多少。
$1\le n,m,\le 10^5,\text{mod}=998244353$。

$\text{Solution:}$

考虑算总和，最后除以 $\dfrac{1}{nm}$。

二项式定理展开：

$$(a_x+b_y)^k=\sum_{i=0}^k \binom{k}{i} a_x^i\times b_y^{k-i}$$

显然是二项式卷积的形式，令 $A(x)=\sum_{i=0}^k \dfrac{\sum_{j=0}^n a_j^k}{i!}$，$B(x)=\sum_{i=0}^k \dfrac{\sum_{j=0}^m b_j^k}{i!}$，然后卷一下就可以了。

再考虑求 $\sum_{j=0}^n a_j^k$ 的部分，也就是序列 $k$ 次方和。

考虑一个值 $a_p$ 的生成函数为：

$$\sum_{i=0}^k a_p^ix^i=\dfrac{1}{1-a_px}$$

那么要求：

$$F(x)=\sum_{i=1}^n \dfrac{1}{1-a_ix}$$

这不好算，但是考虑到：

$$(\ln(1-a_ix))'=\dfrac{-a_i}{1-a_ix}$$

令：

$$G(x)=\sum_{i=1}^n \dfrac{-a_i}{1-a_ix}$$

那么 $F(x)=-G(x)x+n$。又：

$$G(x)=\sum_{i=1}^n \dfrac{-a_i}{1-a_ix}=\sum_{i=1}^n (\ln(1-a_ix))'=(\ln(\prod_{i=1}^n (1-a_ix)))$$

然后 $G(x)$ 可以分治地算，再推出 $F(x)$，求出 $A(x),B(x)$ 即可。

时间复杂度 $\mathcal{O}(n\log^2 n)$。

$\text{Summary:}$

首先对于 $(x+y)^k$ 的形式应考虑二项式定理，从而可以转变为二项式卷积的形式。

接着的操作需要一定的观察，从 $F$ 到 $G$ 的转化是十分巧妙的。因此应对常见函数的求导积分有所了解。

同时，由于 $F$ 是和式，所以在本题的情形下，无法使用大多数的多项式技巧进行优化。因此考虑转变为卷积，也就是变成了 $G(x)$ 中的 $\prod$。与之不同的是付公主的背包一题，同样是利用 $\ln$ 进行卷积与加法之间的转化，但是后者将卷积转化为加法来利用调和级数。