CF891E
mango09
·
·
个人记录
推广一个好玩的
一次操作若将 a_i 减一，则所有数的乘积会少 1\cdot \prod\limits_{j \ne i} a_j，恰好等于答案的增加量。
所以最终答案就是乘积的减少量，即
\prod a_i - \prod (a_i - b_i)
于是问题转化为求 \prod (a_i - b_i) 的期望。
如果对于每一个 a_i 都已知一个确定的 b_i，其中 \sum b_i = k，则可能的操作排列的数量是 \dfrac{k!}{\prod b_i!}，所以期望就是
\dfrac{\dfrac{k!}{\prod b_i!}\cdot \prod (a_i - b_i)}{n^k} = \dfrac{k!}{n^k} \cdot \prod \dfrac{a_i - b_i}{b_i!}
对于后面这个，由于有要求 \sum b_i = k，考虑用多项式搞，然后发现形态长得像 EGF：
\begin{aligned}
F_i(x)
&= \sum_{j = 0}^{+\infty} \dfrac{a_i - j}{j!} x^j \\
&= a_i \cdot \sum_{j = 0}^{+\infty} \dfrac{x^j}{j!} - x \cdot \sum_{j = 0}^{+\infty} \dfrac{x^{j - 1}}{(j - 1)!} \\
&= (a_i - x) e^x
\end{aligned}
那么
\begin{aligned}
\prod_{i = 1}^n \dfrac{a_i - b_i}{b_i!}
&= [x^k] \prod_{i = 1}^n F_i(x) \\
&= [x^k] e^{nx} \prod_{i = 1}^n (a_i - x) \\
&= [x^k] \sum_{j = 0}^{+\infty} \dfrac{(nx)^j}{j!} \prod_{i = 1}^n (a_i - x)
\end{aligned}
我们设
\prod_{i = 1}^n (a_i - x) = \prod_{i = 0}^n f_i x^i
则
\begin{aligned}
\prod_{i = 1}^n \dfrac{a_i - b_i}{b_i!}
&= [x^k] \sum_{j = 0}^{+\infty} \dfrac{(nx)^j}{j!} \prod_{i = 0}^n f_i x^i \\
&= \sum_{i = 0}^{\min(n, k)} \dfrac{f_i n^{k - i}}{(k - i)!}
\end{aligned}
就是右边取 x^i 那么左边就取 x^{k - i}。
对于 f_i，本质上是 n 个一次函数的乘积，直接暴力 O(n^2)。
但问题是最上面的式子中有个 \dfrac{k!}{n^k}，k 太大无法计算，所以我们把式子代回去
\dfrac{k!}{n^k} \cdot \sum_{i = 0}^{\min(n, k)} \dfrac{f_i n^{k - i}}{(k - i)!} = \sum_{i = 0}^{\min(n, k)} \dfrac{f_i k^{\underline{i}}}{n^i}
Code