CF891E Lust

传送门

一次操作对答案的贡献是

我们设等式右侧的减号左边为\(S_1\),右侧为\(S_2\)会得到总贡献为

假设第\(i\)个数被选择\(b_i\)次，那么答案就是

我们只要求后面那部分的期望

将他写成指数生成函数的形式

右边的\(\prod\limits_{i=1}^{n}(a_i-x)\)可以\(O(n^2)\)乘出来，设\(f(x)\)为得到的多项式

所以

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
	inline int read()
	{
		int x=0;char ch,f=1;
		for(ch=getchar();(ch<‘0‘||ch>‘9‘)&&ch!=‘-‘;ch=getchar());
		if(ch==‘-‘) f=0,ch=getchar();
		while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();}
		return f?x:-x;
	}
	const int N=4e5+10,p=1e9+7;
	int n,k,ans,len;
	int fac[N],inv[N];
	int a[N];
	int f[N],g[N],h[N];
	inline void add(int &x,int y)
	{
		x+=y;
		if(x>=p) x-=p;
		if(x<0) x+=p;
	}
	inline int fast(int x,int k)
	{
		int ret=1;
		while(k)
		{
			if(k&1) ret=ret*x%p;
			x=x*x%p;
			k>>=1;
		}
		return ret;
	}
	inline void main()
	{
		n=read(),k=read();
		ans=1;f[0]=1;len=0;
		for(int i=1;i<=n;++i)
		{
			a[i]=read();
			ans=ans*a[i]%p;
			g[0]=a[i],g[1]=-1;
			for(int j=0;j<i;++j)
			{
				for(int k=0;k<=1;++k)
				{
					add(h[j+k],f[j]*g[k]%p);
				}
			}
			for(int j=0;j<=i;++j) f[j]=h[j],h[j]=0;
		}
		for(int tmp=1,i=0;i<=min(n,k);++i,tmp=tmp*n%p)
		{
			int ret=f[i];
			for(int j=k,d=i;d;--d,--j) ret=ret*j%p;
			ret=ret*fast(tmp,p-2);
			add(ans,-ret%p);
		}
		printf("%lld\n",ans);
	}
}
signed main()
{
	red::main();
	return 0;
}

CF891E Lust

原文：https://www.cnblogs.com/knife-rose/p/13045683.html