ABC331G Collect Them All 做题记录

有 $m$ 个卡，第 $i$ 个卡每次抽到的概率都是 $\frac{a_i}{n}$，其中 $n=\sum\limits_{i=1}^m a_i$，求集齐所有卡期望需要多少次，对 $998244353$ 取模。

$1\le n,m\le 10^5$，$1\le a_i\le n$。

首先 min-max 容斥转化为背包。

然后相当于 $\sum\limits_{k=1}^{n}\frac{n}{k}[x^k]\prod\limits_{i=1}^m (1-x^{a_i})$。

把 $\prod\limits_{i=1}^m (1-x^{a_i})$ 转化为 $\exp\left(\sum\limits_{i=1}^m\ln(1-x^{a_i})\right)$。

$\begin{aligned} \ln(1-x^v)'&=\frac{-vx^{v-1}}{1-x^v}\\ &=-\sum\limits_{j=0}^{\infin}vx^{v-1+vj}\\ &=-\sum\limits_{j=1}^{\infin}vx^{vj-1}\\ &=-\sum\limits_{j=1}^{\infin}\frac{vjx^{vj-1}}{j}\\ \end{aligned}$

$\begin{aligned} \int \ln(1-x^v)'dx&=\int -\sum\limits_{j=1}^{\infin}\frac{vjx^{vj-1}}{j}dx\\ &=-\sum\limits_{j=1}^{\infin}\frac{\int vjx^{vj-1}dx}{j}\\ &=-\sum\limits_{j=1}^{\infin}\frac{x^{vj}}{j}\\ &=-\sum\limits_{j=1}^{\infin}\frac{x^{vj}}{j}\\ \end{aligned}$

$\ln(1-x^v)=-\sum\limits_{j=1}^{\infin}\frac{x^{vj}}{j}$

注意到 $-\sum\limits_{j=1}^{\infin}\frac{x^{vj}}{j}$ 在 $\text{mod } x^n$ 意义下只有 $\lfloor\frac{n}{v}\rfloor$ 项非零，枚举 $v$ 即可 $O(n\ln n)$ 算出 $\sum\limits_{i=1}^m\ln(1-x^{a_i})$，然后 $O(n\log n)$ 求 exp 即可。

时间复杂度 $O(m+n\log n)$。