题解 CF891E 【Lust】
skydogli
2020-07-30 08:47:42
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;
}
```