[CF891E] Lust

\(\text{Problem}:\)Lust

\(\text{Solution}:\)

设当前第 \(i\) 个数被减了 \(b_{i}\) 次，对答案的贡献为：

前面的 \(\prod\limits_{i=1}^{n}a_{i}\) 是不变的，现在要求的是后面式子的期望。考虑序列 \(b\) ，满足 \(\sum b_{i}=k\) ，对答案的期望贡献：

发现式子里既有 \(\sum b_{i}=k\)，又有 \(b_{i}!\)，考虑后面 \(\dfrac{a_{i}-b_{i}}{b_{i}!}\) 的 \(\text{EGF}:\)

对于 \(\prod\limits_{i=1}^{n}\dfrac{a_{i}-b_{i}}{b_{i}!}\)，有：

后面这个 \(\prod\limits_{i=1}^{n}(a_{i}-x)\) 有点难以处理，考虑将其转化为 \(\sum\limits_{i=0}^{n}c_{i}x^{i}\) 的形式，有：

现在要求的是 \([x^{k}]G(x)\)：

对于 \(c_{i}\) 的计算，可以暴力展开，在 \(O(n^2)\) 的时间复杂度内解决。总时间复杂度 \(O(n^2)\)。

\(\text{Code}:\)

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=5010, Mod=1e9+7;
inline int read()
{
	int s=0, w=1; ri char ch=getchar();
	while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w=-1; ch=getchar(); }
	while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
	return s*w;
}
int n,K,a[N],c[N];
inline int ksc(int x,int p) { int res=1; for(;p;p>>=1, x=x*x%Mod) if(p&1) res=res*x%Mod; return res; }
signed main()
{
	n=read(), K=read();
	for(ri int i=1;i<=n;i++) a[i]=read();
	c[0]=1;
	for(ri int i=1;i<=n;i++)
	{
		for(ri int j=i;j;j--) c[j]=(c[j]*a[i]-c[j-1]+Mod)%Mod;
		c[0]=c[0]*a[i]%Mod;
	}
	int ans=0;
	for(ri int i=0,fac=1;i<=min(n,K);i++)
	{
		ans=(ans+ksc(ksc(n,i),Mod-2)%Mod*fac%Mod*c[i]%Mod)%Mod;
		fac=fac*(K-i)%Mod;
	}
	printf("%lld\n",(c[0]-ans+Mod)%Mod);
	return 0;
}

[CF891E] Lust

原文：https://www.cnblogs.com/zkdxl/p/14664572.html