Yukicoder No. 1857 Gacha Addiction (解説のみ)

問題: https://yukicoder.me/problems/no/1857

 

$X$が正の整数の時、$E[X] = P(X \ge 1) + P(X \ge 2) + P(X \ge 3) + \cdots$あ成立します。

$P(X \ge k)$のためには、最初の$k-1$回引いた品物が全部違う必要があります。

最初の$k-1$回で決めた順番に品物を引く確率は簡単にそれぞれの積に計算できます。

最初の$k-1$回で順番を決める方法は$k-1$個の品物を決めたあと順番を決めるのでできます。

$P(X \ge k) = (k-1)!\times\sum_{S \subset \{1, \cdots, n\}, |S| = k-1} \left(\prod_{i \in S} p_i\right) $になります。

 

$\prod_{1 \le i \le N} (1+p_ix) $の$x^k$項の係数が$\dfrac{P(X \ge k)}{(k-1)!}$で、これはFFTと分割統治で計算出来ます。

$\prod_{l \le i \le r} (1+p_ix) = \left(\prod_{l \le i \le m} (1+p_ix)\right) \times \left(\prod_{m+1 \le i \le r} (1+p_ix)\right)$でFFTを使って計算すれば、計算量$T$の関して、$T(N) = 2T(N/2) + O(N \log N)$になり、$T(N)=O(N \log^2N)$になります。

 

実装: https://yukicoder.me/submissions/742320