Monotone OR

basince · 2025-05-27 15:59:16 · 题解

设 f_{i} 表示 i=(x\mid s_k)+1 时的方案数，g_i 表示 i=(x\mid s_k) 时的方案数。

暴力转移

设 a_i 表示 s_k\subseteq i 的 k 的数量，可以用高维前缀和求出，转移优化成

可以发现需要半在线求 g,f 的高维前缀和，利用分治的结构转移即可做到 O(n2^n)。

#include<bits/stdc++.h>
#define ri register int
#define fo(i,x,y) for(ri i=(x);i<=(y);++i)
#define fu(i,x,y) for(ri i=(x);i<(y);++i)
#define fd(i,x,y) for(ri i=(x);i>=(y);--i)
using namespace std;
const int N=(1<<24)+5,p=998244353;
int n,m,a[N],b[N],c[N],f[N],g[N];
inline void add(ri &x,ri y){if((x+=y)>=p)x-=p;}
inline void del(ri &x,ri y){if((x-=y)<0)x+=p;}
inline void sol(ri l,ri r,ri d){
    if(r==l+1){
        add(b[l],f[l]);
        f[r]=g[l]=(1ll*a[l]*b[l]%p-c[l]+p)%p;
        b[l]=f[l];c[l]=g[l];
        return;
    }
    ri md=l+r>>1,u=1<<d;
    sol(l,md,d-1);
    fu(i,l,md){
        add(b[i+(1<<d-1)],b[i]);
        add(c[i+(1<<d-1)],c[i]);
    }
    sol(md,r,d-1);
    fu(i,l,md){
        add(b[i+(1<<d-1)],b[i]);
        add(c[i+(1<<d-1)],c[i]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    fo(i,1,m){
        ri x;scanf("%d",&x);
        ++a[x];
    }
    ri w=1<<n;
    fu(i,0,n)fu(j,0,w)
        if(j>>i&1)add(a[j],a[j^(1<<i)]);
    f[0]=1;sol(0,w,n);
    printf("%d",f[w]);
}