CF891E Lust

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 5k | 阅读时长 ≈ 5 分钟

CF891E Lust

传送门

洛谷

题意描述

A false witness that speaketh lies! You are given a sequence containing $ n $ integers. There is a variable $ res $ that is equal to $ 0 $ initially. The following process repeats $ k $ times. Choose an index from $ 1 $ to $ n $ uniformly at random. Name it $ x $ . Add to $ res $ the multiply of all $ a_{i} $ ‘s such that $ 1<=i<=n $ , but $ i≠x $ . Then, subtract $ a_{x} $ by $ 1 $ . You have to find expected value of $ res $ at the end of the process. It can be proved that the expected value of $ res $ can be represented as an irreducible fraction $\frac{P}{Q}$. You have to find $P \times Q^{-1} \ mod \ 1000000007$.

题意翻译

你有n个数$a_1$,$a_2$…$a_n$，要进行k次操作，每次随机选择一个数x，使得$res+=\prod_{i \neq x}a_i$，求最后res值的期望，对1e9+7取模。

输入输出格式

输入格式：

The first line contains two integers $ n $ and $ k $ ( $ 1<=n<=5000 $ , $ 1<=k<=10^{9} $ ) — the number of elements and parameter $ k $ that is specified in the statement. The second line contains $ n $ space separated integers $ a_{1},a_{2},…,a_{n} $ ( $ 0<=a_{i}<=10^{9} $ ).

输出格式：

Output a single integer — the value $P \times Q^{-1} \ mod \ 1000000007$.

输入输出样例

输入样例#1：

2 1
5 5

输出样例#1：

5

输入样例#2：

1 10
80

输出样例#2：

10

输入样例#3：

2 2
0 0

输出样例#3：

500000003

输入样例#4：

9 4
0 11 12 9 20 7 8 18 2

输出样例#4：

169316356

分析

网上的大家似乎都是使用指数型生成函数求解这个问题——然而，这对于Gluttony这种菜鸡来说灰常不友好，于是菜鸡Gluttony觉得需要将B君告诉Gluttony的方法写下来。
首先，发现$\prod_{i \neq x}a_i=a_x\prod_{i \neq x}a_i - (a_x-1)\prod_{i \neq x}a_i$。
每次操作都是满足这个式子的，那么将这$k$的操作的权值加起来（即$res$），就是$\prod_ia_i - \prod_i(a_i-d_i)$，其中$d_i$表示这$k$次操作中$a_i$被减了几次。
我们对这个式子的后面进行展开，即

观看符号整个人都要崩溃了，顺便写一个式子看看就好理解了。比如这个式子

其中第一项的$|S|=\emptyset$。
其中第二项的$|S|={1}$。
其中第三项的$|S|={2}$。
其中第四项的$|S|={1,2}$。
那么考虑在期望下求这个式子

由于操作是随机的，那么对于每个数，我们操作的期望都一样，设这个期望为$E(d)$，即有$E(d_i)=E(d) \ | \ 1\le i \le n$。
那我们在把上面的式子化简一下。

注意到上面的式子每一包含$a$的式子都相当于从序列中取出若干个$a$的和，那么我们记从序列中取出$i$个$a$的和为$v_i$。
那么原式转化为

再带入之前那个鬼畜的式子

这个$v_i$可以使用背包$DP$求出或者生成函数（$FFT$？）求得。
那么现在我们更应该考虑的是怎么求得$E(d^i)$。
先说结论。

开始讲这个式子是怎么来的，首先不考率这个期望的分母，分子就是一个计数问题。
你有一个长度为$k$的随机的数列，每个数都是$[1,n]$，定义一个排列的$t$权值为$1$的个数$\times$ $2$的个数$\times$…$\times$ $t$的个数，对于所有的$t$，所有数列的$t$权值之和。
这个问题又等价于你有一个长度为$k$的随机的数列，每个数都是$[1,n]$，定义一个排列的$t$权值为随意选出$t$的数，满足选出的第$i$个数就是$i$的方案数，求对于所有的$t$，所有数列的$t$权值之和。
这个问题求解办法就是我们考虑先把这$t$的数固定下来，其他的顺便填，即$\prod_{i=k}^{k-t+1}i \times n^{k-t}$，解释一下这个式子，我们挨着填这$t$个数，对于第$1$个数，它有$k$个位置可以填，对于第$2$个数，它有$k-1$个位置可以填，依此类推，就是$\prod_{i=k}^{k-t+1}i$，最后剩下的$k-t$的位置随便填，每个位置有$n$种填法，就是$n^{k-t}$。
那么带入期望的定义式（上面说的$t$相当于下面的$i$）

再带入之前的式子

最后$O(n)$递推即可。

参考资料

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 5010
#define p 1000000007
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int n,K,ans,tot=1,invn,f[maxn];
int add(int x,int y)
{
	return (x+y)%p;
}
int sub(int x,int y)
{
	return (x-y+p)%p;
}
int mul(int x,int y)
{
	return 1ll*x*y%p;
}
int fpow(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1)
			res=mul(res,x);
		x=mul(x,x);
		y>>=1;
	}
	return res;
}
int main()
{
	read(n,K);
	invn=fpow(n,p-2);
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		int t=read<int>();
		tot=mul(tot,t);
		for(int j=i;j>=1;j--)
			f[j]=add(f[j],mul(f[j-1],t));
	}
	int t=1;
	for(int i=0;i<=n&&i<=K;i++)
	{
		if(i&1)
			ans=sub(ans,mul(f[n-i],t));
		else
			ans=add(ans,mul(f[n-i],t));
		t=mul(t,K-i);
		t=mul(t,invn);
	}
	printf("%d\n",sub(tot,ans));
    return 0;
}