题目链接
题目解法
会不了 \(egf\) /ll
我们把贡献变成 \(\prod\limits_{j\neq i}a_j=\prod\limits_{j=1}^na_j-\prod\limits_{j=1}^n (a_i-[i=j])\)
即答案为一开始的乘积 \(-\) \(k\) 次操作之后所有数乘积的期望
因为有顺序,所以用 \(egf\) 的形式表示最后乘积的期望:
\(f_i(x)=\sum\limits_{j=0}^{\infty} \frac{(a_i-j)x^j}{j!}=a_ie^x-xe^x=(a_i-x)e^x\)
\(F(x)=\prod f_i(x)=e^{nx}\prod (a_i-x)\)
后面的东西可以背包暴力求出(或者分治 \(ntt\))
最终的答案形式是:\(\frac{f_i\frac{n^{k-i}}{(k-i)!}\times k!}{n^k}=\frac{f_ik^{\underline {i}}}{n_i}\)
时间复杂度 \(O(n^2)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=5010,P=1e9+7;
int n,k,a[N],f[N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
inline void dec(int &x,int y){ x-=y;if(x<0) x+=P;}
int qmi(int x,int y){
int res=1;for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}
return res;
}
int main(){
read(n),read(k);
int ini=1;
F(i,1,n) read(a[i]),ini=1ll*ini*a[i]%P;
f[0]=1;
F(i,1,n) DF(j,i,0){
f[j]=1ll*f[j]*a[i]%P;
if(j) dec(f[j],f[j-1]);
}
int ans=0,mul=1,inv=qmi(n,P-2);
F(i,0,min(n,k)){
inc(ans,1ll*f[i]*mul%P);
mul=1ll*mul*(k-i)%P*inv%P;
}
dec(ini,ans);
printf("%d\n",ini);
return 0;
}
标签:ch,int,题解,CF891E,Lust,1ll,ini,prod,define
From: https://www.cnblogs.com/Farmer-djx/p/18388815