CF891E Lust

---

鸽子更博了

Orz Itst

神仙结论：最后的答案是一开始的\(\prod a_i\)减去最后的\(\prod a_i\)。证明感性理解。Orz Itst

然后可以套生成函数，如果第\(i\)个数选了\(c_i\)次那么有\(\frac{k!}{\prod c_i!}\)种选法。所以\(f_i(x)=\sum_{j\ge 0}x^j\frac{a_i-j}{j!}\)，可以套\(e\)进去。Orz Itst

多项式忘光了，Orz Itst

\(f_i(x)=\sum_{j\ge 0}x^j\frac{a_i-j}{j!}=e^x(a_i-x)\)

要求\(k!\frac{1}{n^k}[x^k]\prod f_i(x)=k![x^k]e^{nx}\prod(a_i-x)\)。

\(\prod(a_i-x)\)是个\(n\)次多项式，那么只要求\(e^{nx}\)的第\(k-n\)到\(k\)项即可。

有一个\(k!\)不好算，注意\([x^i]e^{nx}=\frac{n^ix^i}{i!}\)，下面的阶乘和\(k!\)约分一下就可以算了。

#include
    
     #define il inline#define vd void#define mod 1000000007il int gi(){    int x=0,f=0;char ch=getchar();    while(!isdigit(ch))f^=ch=='-',ch=getchar();    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return f?-x:x;}il int pow(int x,int y){    int ret=1;    while(y){        if(y&1)ret=1ll*ret*x%mod;        x=1ll*x*x%mod;y>>=1;    }    return ret;}int c[5010];int main(){#ifdef XZZSB    freopen("in.in","r",stdin);    freopen("out.out","w",stdout);#endif    int n=gi(),k=gi(),mul=1;    c[0]=1;    for(int i=1;i<=n;++i){        int a=gi();mul=1ll*a*mul%mod;        for(int j=n;~j;--j)c[j+1]=(c[j+1]-c[j]+mod)%mod,c[j]=1ll*c[j]*a%mod;    }    int ans=0,invn=pow(n,mod-2);    for(int i=0,pn=1,fc=1;i<=n;fc=1ll*fc*(k-i)%mod,pn=1ll*pn*invn%mod,++i)ans=(ans+1ll*c[i]*fc%mod*pn%mod)%mod;    printf("%d\n",(mul-ans+mod)%mod);    return 0;}