[2018HN省队集训D8T3] 水果拼盘

时间:2024-04-03 17:33:56

[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)\).

参考代码

#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;
}

[2018HN省队集训D8T3] 水果拼盘