[2018HN省队集训D8T3] 水果拼盘
题意
给定 $n$ 个集合, 每个集合包含 $[1,m]$ 中的一些整数, 在这些集合中随机选取 $k$ 个集合, 求这 $k$ 个集合的并集的权值的期望.
一个集合的权值定义为, 对于所有 $[1,m]$ 的整数, 若集合中含有 $i$ 则产生 $a_i$ 的贡献, 否则产生 $b_i$ 的贡献.
$n\le 1\times 10^5, m\le 18,k\le 25$
题解
好像只有我一个写了一些玄学FWT操作…别人都是组合数直接碾的qaq
显然我们可以通过求所有最终集合的生成概率来计算出最终期望. 而这个概率显然就是个或卷积的形式.
于是我们可以FWT一发.
接着我们发现直接FWT卷 $k$ 次可能会有重复的方案. (就像[BZOJ 3771] Triple那题). 于是我们需要考虑容斥.
然而这次是广义容斥, 普通二项式反演出来是假的.
stdcall&栋栋说过广义容斥瞎换一波系数就过了, 于是思考一些奇怪的东西来凑容斥系数.
FWT卷 $k$ 次后得到的方案数是 $n^k$, 而我们实际上需要的不重复的方案数应该是 $n^{\underline k}$ (卷积出来的方案有序, 要自带一个全排列), 那么我们需要用一些玄学系数用 $n^k$ 凑出 $n^{\underline k}$.
注意到其实 $n^{\underline k}$ 就是一个普通多项式, 那么我们可以直接算出这个多项式的每一项系数把它作为容斥系数.
实际上就是带符号第一类斯特林数. 用这个系数容斥一下就好了.
FWT一次后的点值可以重复使用, 所以总时间复杂度是 $O(\sum|S|+(k+m)2^m)$.
参考代码
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include <bits/stdc++.h>
const int MAXK=27;
const int MAXL=1e6+10;
const int MOD=998244353;
int n;
int m;
int k;
int a[MAXL];
int pw[MAXK];
int ans[MAXL];
int cof[MAXK];
int c[MAXK][2];
void FWT(int*,int);
void IFWT(int*,int);
inline int ReadInt();
inline int Pow(int,int,int);
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++)
scanf("%d",c[i]+1);
for(int i=0;i<m;i++)
scanf("%d",c[i]);
cof[0]=1;
for(int i=0;i<k;i++){
for(int j=i+1;j>0;j--)
cof[j]=(cof[j-1]-1ll*cof[j]*i%MOD+MOD)%MOD;
cof[0]=(MOD-1ll*cof[0]*i%MOD)%MOD;
}
for(int i=0;i<n;i++){
int cnt=ReadInt(),s=0;
while(cnt--)
s|=(1<<(ReadInt()-1));
++a[s];
}
int maxs=1<<m;
FWT(a,maxs);
pw[0]=1;
for(int s=0;s<maxs;s++){
for(int i=1;i<=k;i++)
pw[i]=1ll*pw[i-1]*a[s]%MOD;
for(int i=0;i<k;i++)
ans[s]=(ans[s]+1ll*pw[k-i]*cof[k-i])%MOD;
}
IFWT(ans,maxs);
int cnt=0;
int sum=0;
for(int s=0;s<maxs;s++){
(cnt+=ans[s])%=MOD;
for(int i=0;i<m;i++)
sum=(sum+1ll*c[i][(s>>i)&1]*ans[s])%MOD;
}
printf("%lld\n",1ll*sum*Pow(cnt,MOD-2,MOD)%MOD);
return 0;
}
inline void FWT(int* a,int len){
for(int i=1;i<len;i<<=1)
for(int j=0;j<len;j+=(i<<1))
for(int k=0;k<i;k++){
a[j+k+i]+=a[j+k];
a[j+k+i]=(a[j+k+i]>=MOD?a[j+k+i]-MOD:a[j+k+i]);
}
}
inline void IFWT(int* a,int len){
for(int i=1;i<len;i<<=1)
for(int j=0;j<len;j+=(i<<1))
for(int k=0;k<i;k++){
a[j+k+i]-=a[j+k];
a[j+k+i]=(a[j+k+i]<0?a[j+k+i]+MOD:a[j+k+i]);
}
}
inline int ReadInt(){
int x=0;
register char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
inline int Pow(int a,int n,int p){
int ans=1;
while(n>0){
if(n&1)
ans=1ll*a*ans%p;
a=1ll*a*a%p;
n>>=1;
}
return ans;
}
|
