题解 CF891E 【Lust】

skydogli

2020-07-30 08:47:42

Solution

EGF入门题。 [EGF入门好文](https://zhuanlan.zhihu.com/p/53079223) 如果你没有和我一样读错题的话,你会发现每次答案的增加量等于$\prod a_i$的减少量,那么设 $b_i$ 为最后第 $i$ 个数减了多少次 $1$,答案其实就是 $\prod a_i-\prod (a_i-b_i)$。 所以我们现在考虑如何求$\prod (a_i-b_i)$的期望。 考虑对于一组 $\sum b_i=k$ 对期望的贡献我们如何计算。 $$ \mathbb{E}=\frac{1}{n^k} \frac{k!}{\prod\limits_{i=1}^n b_i!}\prod_{i=1}^n (a_i-b_i)=\frac{k!}{n^k}\prod_{i=1}^n \frac{a_i-b_i}{b_i!} $$ 其中, $n^k$ 表示所有可能的操作序列数,$\frac{k!}{\prod\limits_{i=1}^n b_i!}$ 是众所周知的将 $n$ 种不同颜色,个数分别为 $b_1\dots b_n$,总数为 $k$ 的小球摆成一排的方案数。 然后我们考虑后面这坨 $\prod \frac{a_i-b_i}{b_i!}$ 能不能用生成函数做。构造指数型生成函数 $$\hat f_i(x)=\sum_{j=0}^{\infty}\frac{a_i-j}{j!}x^j=\sum_{j=0}^{\infty}\frac{a_i}{j!}x^j-\frac{x\cdot x^{j-1}}{(j-1)!}=(a_i-x)e^x$$ 对于整体来说 $$\hat F(x)=\prod_{i=1}^n \hat f_i=e^{nx}\prod_{i=1}^n(a_i-x)$$ 我们要求出$[x^k]\hat F(x)$,好像有点可做了。 令 $$G(x)=\prod_{i=1}^n (a_i-x)=\sum_{i=0}^{n}c_ix^i$$ 然后发现 $$[x^k]\hat F(x)=\sum_{i=0}^n c_i\frac{n^{k-i}}{(k-i)!}$$ 咱们回溯一下发现 $$\mathbb{E}=\sum_{i=0}^n c_i\frac{k!}{(k-i)!n^i}$$ ohhhhhhh 最后输出 $c_0-\mathbb{E}$ 即可。这题 $n$ 很小,$G(x)$ 直接 $O(n^2)$ 暴力算出来就好了。 ```cpp #include<bits/stdc++.h> using namespace std; #define int long long #define Mod 1000000007 #define MN 5005 int ksm(int a,int x){ int ans=1,w=a; while(x){ if(x&1)ans=ans*w%Mod; w=w*w%Mod; x>>=1; } return ans; } int n,k,a[MN],f[MN]; signed main(){ scanf("%lld%lld",&n,&k); f[0]=1; for(int i=1;i<=n;++i){ scanf("%lld",&a[i]); for(int j=i;j;--j){ f[j]=(f[j]*a[i]-f[j-1]+Mod)%Mod; } f[0]=f[0]*a[i]%Mod; } int res=0,tmp=1,inv=ksm(n,Mod-2); for(int i=0;i<=n;++i){ res=(res+f[i]*tmp)%Mod; tmp=tmp*(k-i)%Mod*inv%Mod; } printf("%lld\n",(f[0]-res+Mod)%Mod); return 0; } ```