【题解】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$ 进行卷积与加法之间的转化,但是后者将卷积转化为加法来利用调和级数。

添加新评论