CF891E Lust 题解

本文版权归 Azazel 与博客园共有，欢迎转载，但需保留此声明，并给出原文地址，谢谢合作。

原文地址：https://www.cnblogs.com/Azazel/p/15185109.html

(~~~~) ~~为什么会有正经题目叫这个名字并且文题无关~~

题意

(~~~~) 你有 (n) 个数 (a_1,a_2,dots,a_n) ，进行 (k) 次操作，每次等概率在 ([1,n]) 中选择一个数 (x) ，使得 (a_x-1) 并产生除 (a_x) 外其他数乘积的贡献。

题解

(~~~~) 首先发现产生贡献的式子很奇怪，对于某个 (x) ，其单次产生的贡献为 (prod_{i=1}^n [i ot= x] (a_i-b_i)) ，其中 (b_i) 表示在该操作之前 (i) 被选择过多少次。全局的贡献则还需要枚举 (k) 次 (x) 。

(~~~~) 这个式子并不优美，那么我们考虑把它换成优美的形式：

[large prod_{i=1}^n a_i-prod_{i=1}^n (a_i-b_i) ]

(~~~~) 这显然是正确的全局贡献，原因略过。

(~~~~) 那么我们就可以改为求 (E[prod_{i=1}^n a_i-prod_{i=1}^n (a_i-b_i)]) ，更具体地，我们应求出 (E[prod_{i=1}^n (a_i-b_i)])。

(~~~~) 对于任意已知的 ({b}) ，其产生的概率为 (dfrac{frac{k!}{prod_{i=1}^n b_i!}}{n^k}) ，即共有 (n^k) 种产生的 (x) 的序列，而有可重集的排列方案即为分子。故

[large E[prod_{i=1}^n (a_i-b_i)]=dfrac{frac{k!}{prod_{i=1}^n b_i!}}{n^k} prod_{i=1}^n (a_i-b_i)=dfrac{k!}{n^k}prod_{i=1}^ndfrac{a_i-b_i}{b_i!} ]

(~~~~) ~~然后就是我不会的仙术了。~~

(~~~~) 对于后面一堆 (prod) ，我们使用生成函数进行计算。记： (f_i(x)=sum_{j=0}^{infty}(a_i-j)dfrac{x^j}{j!}) ，对生成函数化一波式子：

[large f_i(x)=sum_{j=0}^{infty}dfrac{x^j}{j!}a_i-dfrac{x^{j-1}}{(j-1)!}x=e^x(a_i-x) ]

(~~~~) 然后代回式子：

[large prod_{i=1}^n f_i(x)\ large =prod_{i=1}^n e^x(a_i-x)\ =large e^{nx}prod_{i=1}^n (a_i-x) ]

(~~~~) 记最后 (prod_{i=1}^n (a_i-x)=sum_{i=0}^n c_ix^i) ，这可以 (n^2) 求得，并代回答案的式子：

[large dfrac{k!}{n^k} e^{nx}sum_{i=0}^n c_ix^i\ large = dfrac{k!}{n^k}sum_{i=0}^nc_ix^isum_{j=0}^{infty}dfrac{n^j}{j!}x^j ]

(~~~~) 由于 (sum_{i=1}^n b_i=k) ，所以我们只需要 ([x^k]) 部分：

[large dfrac{k!}{n^k} sum_{i=0}^n c_idfrac{n^{k-i}}{(k-i)!}x^k\ large sum_{i=0}^n c_idfrac{k!}{n^i(k-i)!} ]

(~~~~) 可以求了！

代码

查看代码

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int MOD=1e9+7;
ll a[5005],b[5005],Pow[5005];
ll qpow(ll A,ll B)
{
	ll ret=1;
	while(B)
	{
		if(B&1) ret=ret*A%MOD;
		B>>=1;A=A*A%MOD;
	}
	return ret;
}
int main() {
	int n,k;ll Pro=1;
	scanf("%d %d",&n,&k);
	if(n==1)
	{
		printf("%d",k);
		return 0;
	}
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),Pro=Pro*a[i]%MOD;
	b[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j>=1;j--) b[j]=(b[j]*a[i]%MOD-b[j-1]+MOD)%MOD;
		b[0]=b[0]*a[i]%MOD;
	}
	ll Fac=1,Ans=0;Pow[0]=1;
	for(int i=1;i<=n;i++) Pow[i]=Pow[i-1]*n%MOD;
	for(int i=0;i<=n;i++)
	{
		Ans=(Ans+b[i]*Fac%MOD*qpow(Pow[i],MOD-2)%MOD)%MOD;
		Fac=Fac*(k-i)%MOD;
	}
	printf("%lld",(Pro-Ans+MOD)%MOD);
	return 0;
}