题目大意
有n个数，进行k轮操作：随机一个i，让\(a_i\)减1，然后ans加上\(\Pi_{j\neq i}a_i\)。
求ans的期望。分析
发现，造成的伤害就是原来的ai的积减去k轮操作后的ai的积（其实我在看题解前根本没发现）。
题目就变成了求k轮操作后的ai的积的期望。 设ai经过了k轮操作减去了bi\[E(\Pi_{i=1}^{n}(a_i-b_i))=\dfrac{1}{n^k}\sum_{\sum_{i=1}^{n}b_i=k}\Pi_{i=1}^{n}(a_i-b_i)(a_i-b_i)C_{k}^{b_1}C_{k-b_1}^{b_2}C_{k-b_1-b_2}^{b_3}...\]\[=\dfrac{1}{n^k}\sum_{\sum_{i=1}^{n}b_i=k}\Pi_{i=1}^{n}(a_i-b_i)(a_i-b_i)\dfrac{k!}{\Pi_{i=1}^{n}b_i!}\] 考虑如何求\[\sum_{\sum_{i=1}^{n}b_i=k}\Pi_{i=1}^{n}(a_i-b_i)(a_i-b_i)\dfrac{1}{\Pi_{i=1}^{n}b_i!}\] 设生成函数\[F_i(x)=\sum_{j=0}^{\infty}\dfrac{a_i-j}{j!}x^j=\sum_{j=0}^{\infty}\dfrac{a_i}{j!}x^j-\sum_{j=0}^{\infty}\dfrac{1}{(j-1)!}x^j=(a_i-x)e^x\] 于是就\[=\Pi_{i=1}^{n}F_i(x)=e^{nx}\Pi_{i=1}^{n}(a_i-x)\] 我们就要求出\(e^{nx}\Pi_{i=1}^{n}(a_i-x)\)的第k项的系数\(\Pi_{i=1}^{n}(a_i-x)\)就可以用分治FFT来求。 然后对于\(\Pi_{i=1}^{n}(a_i-x)\)第i项乘上\(e^{nx}\)第k-i项加起来就是\(e^{nx}\Pi_{i=1}^{n}(a_i-x)\)的第k项的系数了。#include#include #include #include #include #include #include #include