正題

題目鏈接:https://www.luogu.com.cn/problem/CF891E

---

題目大意

$n$個數(shù)字的一個序列$a_i$，每次隨機選擇一個讓它減去一。然后貢獻加上所有其他$a_i$的乘積。

執(zhí)行$k$次，求貢獻答案。

$1\le n\le 5000,0\le a_i,k\le 10^9$

---

解題思路

這個操作很麻煩，但是其實答案就是開始時所有$a_i$的乘積減去結束時所有$a_i$的乘積。

設第$i$個數(shù)減去了$b_i$次，就是求${\prod }_{i=1}^n{a}_i?{\prod }_{i=1}^n(a_i?b_i)$的期望，考慮怎么求后面那個東西。

推一下式子不難發(fā)現(xiàn)對于一組$b_i$對期望的貢獻就是
$$\frac{1}{n^k}\frac{k!}{{\prod }_{i=1}^n(b_i!)}\prod _{i=1}^n(a_i?b_i)$$
（總方案×可重排方案×貢獻）
把${\prod }_{i=1}^n(b_i!)$丟進去會有很神奇的結果
$$?\frac{k!}{n^k}\prod _{i=1}^n\frac{a_i?b_i}{b_i!}$$
因為每種方案都要求和，后面那個東西顯然可以生成函數(shù)搞，設
$$f_z(x)=\sum _{i=0}^n(a_z?i)\frac{x^i}{i!}=\sum _{i=0}^{\infty }{a}_z\frac{x^i}{i!}?\sum _{i=0}^{\infty }i\frac{x^i}{i!}$$

好像就搞不動了，前面那個是$a_z{e}^x$，其實后面那個把$i$抵消掉階乘就是$x{e}^x$
$$f_z(x)=(a_z?x)e^x$$
然后$F={\prod }_{i=1}^n{f}_z$，可以暴力$O(n^2)$乘出${\prod }_{i=1}^n(a_z?x)$這部分，記為${\sum }_{i=0}^{\infty }{c}_i{x}^i$。

然后展開后面的$e^x$就有
$$F(x)[x^k]=\sum _{i=0}^k{c}_i\frac{n^{k?i}}{(k?i)!}$$
然后
$$ans=\sum _{i=0}^k{c}_i\frac{k!}{(k?i)!n^i}$$

就好了，時間復雜度$O(n^2)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5100,P=1e9+7; ll n,k,f[N],ans; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } signed main() {scanf("%lld%lld",&n,&k);f[0]=1;for(ll i=1;i<=n;i++){ll x;scanf("%lld",&x);for(ll j=i;j>=1;j--)f[j]=(f[j]*x-f[j-1]+P)%P;f[0]=f[0]*x%P;}ll tt=1,inv=power(n,P-2);for(ll i=0;i<=n;i++){ans=(ans+f[i]*tt%P)%P;tt=tt*inv%P*(k-i)%P;}printf("%lld\n",(f[0]-ans+P)%P);return 0; }

總結

以上是生活随笔為你收集整理的CF891E-Lust【EGF】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。