CF891E Lust 生成函数

传送门


设在某一次操作之后的(a)数组变为了(a')数组,那么(prodlimits_{i eq x} a_i = prod a_i - prod a_i')。那么就不难发现我们需要求的是进行这(k)次操作之后的(a)数组所有数的乘积的期望值。

注意到当第(i)个数被减去(p_i)次,那么方案数就是(frac{k!}{prod p_i!}),那么考虑指数型生成函数求解。那么第(i)个数的生成函数就是(sumlimits_{j geq 0} frac{a_i - j}{j!}x^j = (a_i - x)e^x)。那么答案就是(k![x^k]e^{nx}prod (a_i - x))。暴力求出(prod (a_i - x))的表示,求出它的每一项对应的(e^{nx})的项的系数,然后就可以求出这个值了。值得注意的是(k!)太大,但是(e^{nx})中也有一个阶乘,这两个可以进行抵消使得需要计算的量在(O(n))范围内。复杂度(O(n^2))

代码

原文地址:https://www.cnblogs.com/Itst/p/11336534.html