526互联

CF1842G Tenzing and Random Operations 思考

发布时间 2023-07-20 09:57:54作者: A_zjzj

借鉴了一下 namelessgugugu 的想法，妙妙题。

link

这个神奇工具的构造确实挺妙的，非常好的思维题，在此记录一下

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e3+10,mod=1e9+7;
int n,m,v,a[N];
int f[N][N];
ll qpow(ll x,ll y=mod-2){
	ll ans=1;
	for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
	return ans;
}
int main(){
	freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m>>v;
	for(int i=1;i<=n;i++)cin>>a[i];
	f[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			f[i+1][j]=(f[i+1][j]+1ll*f[i][j]*a[i+1])%mod;
			f[i+1][j]=(f[i+1][j]+1ll*f[i][j]*v%mod*j)%mod;
			f[i+1][j+1]=(f[i+1][j+1]+1ll*f[i][j]*(i+1)%mod*(m-j)%mod*v)%mod;
		}
	}
	int ans=0,iv=qpow(n),now=1;
	for(int i=0;i<=n;i++,now=1ll*now*iv%mod){
		ans=(ans+1ll*f[n][i]*now)%mod;
	}
	cout<<ans;
	return 0;
}