题解：P13275 [NOI 2025] 集合

· · 题解

赛时完全不知道怎么做，把三方暴力 dp 的 O(8^n) 卡过了 n\le 10 带多测，然后最后一个小时才看出来有用的容斥，喜提没做完。

考虑这个特殊性质 B，大概就是让你把系数凑成 a_i+1 状物。但是完全不知道怎么凑啊？它看上去就像是一个选一个或者不选的组合意义。

考虑随机找个方向容斥。第一个想法是对着 P\cap Q 容斥，但是我场上浪费了两个小时毫无进展。

记 f(P) 为 P 中元素与和，w(P) 为 P 中元素 a_i 乘积。对于整数 x\in[0,2^n)，记 x_i 为 \lfloor\frac{x}{2^i}\rfloor\bmod 2，即二进制下第 i 位。

考虑尝试对着 f(P)=f(Q) 容斥。一个无敌的想法是考虑 A=f(P)-f(Q),B=f(Q)-f(P)（这里的减法视作集合减法，即 S-T 中存在元素 x 当且仅当 S 中存在 T 中不存在，此处即 A 表示 f(P)_i=1,f(Q)_i=0 的 i 的集合，B 同理）。

我们直接容斥 A 和 B！枚举 A,B，容斥系数 (-1)^{\mid A\mid+\mid B\mid}，表示对于 A 中的位，要求 P 所有数在这一位不含 0，Q 至少存在一个这一位是 0 的；对于 B 中的位，要求 Q 所有数在这一位不含 0，P 至少存在一个这一位是 0 的。

考虑对于“至少存在一个”继续容斥。枚举 C\subset A,D\subset B 表示容斥：对于 C 中的位，Q 这一位不含 0（本来是 A 中的位 Q 这一位得存在一个 0，枚举子集钦定不成立的容斥）；对于 D 中的位，P 这一位不含 0。容斥系数 (-1)^{\mid C\mid+\mid D\mid}。这里的限制变成对于 A\cup D 的位，P 这一位没 0；B\cup C 的位，Q 这一位没 0。

写出来相当于：

\sum_{C\subset A,D\subset B,A\cap B=\empty}\sum_{(A\cup D)\in f(P)}\sum_{(B\cup C)\in f(Q)}[P\cap Q=\empty]w(P)w(Q)

这里 a\in b 表示二进制下 a 是 b 的子集。

假设你以及枚举了 A,B,C,D，考虑一个数 i 可以放在哪里（三种选择，放 P，放 Q，都不放）。如果 (A\cup D\cup B\cup C)\in i，则显然贡献是 2a_i+1；如果上述不满足，且满足 (A\cup D)\in i 或 (B\cup C)\in i，则贡献是 a_i+1；否则贡献是 1。

这里“如果上述不满足”的限制比较唐。在性质 B 中 a_i\neq -1，也就是说 a_i+1 存在逆元。记 g(s) 表示 \prod_{s\in i}(a_i+1)，h(s) 表示 \prod_{s\in i}\frac{2a_i+1}{a_i+1}，则贡献可以写为 h(A\cup B\cup C\cup D)g(A\cup D)g(B\cup C)。

预处理 g,h 可以简单高维后缀积，O(2^nn)。然后暴力做是枚举 A,B,C,D，这里分析一下每一位是 1 的可能是：A,AC,B,BD,\empty，所以复杂度是 O(5^n)。

考虑优化也很容易，如果先枚举 A,B，则 C,D 是独立的，复杂度 O(4^n)。

如果先枚举 A,D，然后高维前缀和预处理对于每一组 (A,B) 的 D 的贡献和，则复杂度 O(3^nn)。考场上止步于此了，啊啊啊。

注意到人类智慧。我们的贡献只和 A\cup D 和 B\cup C 有关。如果枚举这两个，那唯一的问题就是如何处理 A\cap B=\empty？可以发现 A\cap B 的部分一定属于 (A\cup D)\cap(B\cup C)。而这里的每一位都可以划给 AD 和 BC，所以竟然直接乘上一个 2^{\mid (A\cup D)\cap(B\cup C)\mid} 就好了！！！

记 s=A\cup D,t=B\cup C。重写一下式子：

\sum_{s,t}(-2)^{\mid s\mid+\mid t\mid}2^{-|S\cup T|}g(s)g(t)h(s\cup t)

注意到 s,t 独立，我们直接做或卷积，所以做到了 O(2^nn)。

但是这里 h 的定义有逆元，但是逆元不一定存在，只能通过性质 B。那咋办。

其实很好做，我们用 a\times M^b 的形式存储一个数，其中 M 是模数。注意到我们只需要做加减乘除。加法的时候令 b 为两个里的小的那个，乘除的时候把 a 乘起来，b 加起来就好了。

这种题代码都很好写。

#include<bits/stdc++.h>
#define MOD 998244353
#define int long long
#define REP(i,a,n) for(int i=a;i<(int)(n);++i)
#define pb push_back
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define cntbit(x) __builtin_popcount(x)
using namespace std;
int qpow(int x,int y){
    int res=1;
    while(y)res=y&1? res*x%MOD:res,x=x*x%MOD,y>>=1;
    return res;
}
int ID;
struct number{
    int x;
    int c;
    void operator =(int y){
        if(y%MOD==0)x=1,c=1;
        else x=y,c=0;
    }
    void operator *=(number a){
        (x*=a.x)%=MOD;
        (c+=a.c)%=MOD;
    }
    void operator *=(int a){
        (x*=a)%=MOD;
    }
    void operator +=(number a){
        int r=min(c,a.c);
        x=((c==r)*x+(a.c==r)*a.x)%MOD,c=r;
    }
    void operator -=(number a){
        int r=min(c,a.c);
        x=((c==r)*x-(a.c==r)*a.x)%MOD,c=r;
    }
};
int n;
int a[1100000];
number f[1100000],g[1100000];
void Main() {
    cin>>n;
    REP(i,0,(1<<n))cin>>a[i];
    REP(i,0,(1<<n))f[i]=a[i]+1;
    REP(i,0,n){
        for(int j=(1<<n)-1;j>=0;--j)if(!((j>>i)&1)){
            f[j]*=f[j|(1<<i)];
        }
    }
    REP(i,0,(1<<n))f[i]*=qpow(-2,cntbit(i));
    REP(j,0,n){
        REP(i,0,(1<<n))if((i>>j)&1){
            f[i]+=f[i^(1<<j)];
        }
    }
    REP(i,0,(1<<n)){
        f[i]*=f[i];
    }
    REP(j,0,n){
        for(int i=(1<<n)-1;i>=0;--i)if((i>>j)&1){
            f[i]-=f[i^(1<<j)];
        }
    }
    REP(i,0,(1<<n)){
        if(a[i]==MOD-1){
            g[i]={a[i],-2};
        }else g[i]=(a[i]*2+1)*qpow(a[i]+1,(MOD-2)*2)%MOD;
    }
    REP(i,0,n){
        for(int j=(1<<n)-1;j>=0;--j)if(!((j>>i)&1)){
            g[j]*=g[j|(1<<i)];
        }
    }
    int ans=0;
    REP(i,0,(1<<n)){
        f[i]*=g[i];
        if(f[i].c)continue;
        int co=qpow((MOD+1)/2,cntbit(i))*f[i].x;
        (ans+=co)%=MOD;
    }
    (ans+=MOD)%=MOD;
    cout<<ans<<'\n';
}
signed main(){
    int tc;
    cin>>ID>>tc;
    while(tc--)Main();
    return 0;
}