题解：P13275 [NOI2025] 集合

· · 题解

NOI 2025 折戟沉沙！

给定 n,a_0,a_1,\cdots,a_{2^n-1}，定义数的 \sube 表示二进制属于，集合的属于记号保持原意。

定义全集 U=\{0,1,\cdots,2^n-1\},\forall S\sube U 定义 f(S)=\mathop{\text{AND}}\limits_{x\in S}\,x，特别的 f(\varnothing)=2^n-1​。

定义 \pi(S)=\prod\limits_{x\in S}a_x,\pi(\varnothing)=1。

ans=\sum\limits_{S,T\sube U,S\cap T=\varnothing}[f(S)=f(T)]\pi(S\cup T)

对 p=998244353 取模，2\le n\le 20,a_i\in [0,p)。

部分分：保证 a_i\ne p-1。

本题做法来自国家集训队 rk.9 hhoppitree，太大神！

思考：考虑 f 的相等肯定是无法刻画的，我们容易刻画的是 x\sube f(S)\Leftrightarrow S\sube S_x，其中超集 S_x=\{y:x\sube y\}。

于是有经典容斥：[P=Q]=\sum\limits_{A\sube P,B\sube Q} (-1)^{|A|+|B|}2^{|A\cap B|}。

带入：

ans=\sum_{A,B}(-1)^{|A|+|B|}2^{|A\cap B|}\sum\limits_{S\sube S_A,T\sube S_B} [S\cap T=\varnothing]\pi(S\cup T)

枚举 C=A\cap B：

ans=\sum_{A,B,C\ 两两不交}(-1)^{|A|+|B|}2^{|C|}\sum\limits_{S\sube S_{A\cup C},T\sube S_{B\cup C}} [S\cap T=\varnothing]\pi(S\cup T)

处理 \sum\limits_{S\sube S_{A\cup C},T\sube S_{B\cup C}} [S\cap T=\varnothing]\pi(S\cup T) 这个东西的常见手段是：

对 S_{A\cup C}\cup S_{B\cup C} 中的每个元素单独考虑放在 S 还是 T 还是丢弃。

定义 L=A\cup B\cup C,D=S_{A\cup C}-S_L,E=S_{B\cup C}-S_L。

于是这部分答案为：

\begin{aligned}\prod\limits_{i\in D}(1+a_i)\prod\limits_{i\in E}(1+a_i)\prod\limits_{i\in L}(1+2a_i)&=\prod\limits_{i\in S_{A\cup C}}(1+a_i)\prod\limits_{i\in S_{B\cup C}}(1+a_i)\prod\limits_{i\in S_L}\dfrac{1+2a_i}{(1+a_i)^2}\\&=f(A\cup C)f(B\cup C)g(A\cup B\cup C)\end{aligned} ans=\sum_{A,B,C\ 两两不交}(-1)^{|A|+|B|}2^{|C|}f(A\cup C)f(B\cup C)g(A\cup B\cup C)

做点小变换 (-1)^{|A|+|B|}=(-1)^{|A\cup C|}\cdot(-1)^{|B\cup C|},2^{|C|}=2^{|A\cup C|+|B\cup C|-|A\cup B\cup C|} 后有：

ans=\sum_{A,B,C\ 两两不交}f(A\cup C)f(B\cup C)g(A\cup B\cup C) \\ f(A)=(-2)^{|A|}\prod\limits_{x\in S_A}(1+a_x) \\ g(A)=2^{-|A|}\prod\limits_{x\in S_A}\dfrac{1+2a_x}{(1+a_x)^2}

注意到 A\cup B\cup C=(A\cup C)\cup (B\cup C)，就是一个或卷积的形式，有：

ans=\sum\limits_{R}g(R)\sum\limits_{P\mid Q=R}f(P)f(Q)

若没有 a_i=p-1 则 f,g 直接预处理，复杂度 \mathcal{O}(n2^n)。

若存在 a_i=p-1，我们如下变换：(1+a_i)\to x,\dfrac{1+2a_i}{(1+a_i)^2}\to\dfrac{2x-1}{x^2}，其中 x \to 0。

注意到经典结论，\lim\limits_{x\to 0}\frac{f(x)}{g(x)} 是两个多项式最低次项的比值。

于是我们在或卷积的时候顺便记录 x 项造成的多项式分数的最低次项，合并直接合并即可。

由于只需要最低次，合并是 \mathcal{O}(1) 的，复杂度 \mathcal{O}(n2^n)。

代码很短。

// 洛谷 P13275
// https://www.luogu.com.cn/problem/P13275
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
#define pc __builtin_popcount
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
inline int rd()
{
    int x=0;char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
    return x;
}
const int N=1<<20|5,mod=998244353,I2=(mod+1)>>1,_2=mod-2;
int C,n,m,a[N],p[23],q[23],ans;P f[N],g[N];
inline void ad(int &x,int y){x+=y;(x>=mod)&&(x-=mod);}
inline int ksm(int x,int p=mod-2){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline P R(P A){return {A.fi,mod-A.se};}
inline void operator+=(P &A,P B){
    if(A>B) swap(A,B);
    if(A.fi==B.fi) ad(A.se,B.se);
}
inline void operator*=(P &A,P B){A={A.fi+B.fi,1ll*A.se*B.se%mod};}
inline void operator*=(P &A,int t){A={A.fi,1ll*A.se*t%mod};}
int main()
{
    C=rd(),C=rd();
    for(int i=*p=*q=1;i<=20;i++) p[i]=1ll*I2*p[i-1]%mod,q[i]=1ll*_2*q[i-1]%mod;
    while(C--)
    {
        n=rd();m=1<<n;ans=0;
        for(int i=0;i<m;i++) a[i]=rd();
        for(int i=0,x;i<m;i++)
        {
            if(a[i]==mod-1) f[i]={1,1},g[i]={-2,mod-1};
            else f[i]={0,x=1+a[i]},x=ksm(x),g[i]={0,(1+2ll*a[i])*x%mod*x%mod};
        }
        for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(j>>i&1)
            f[j^(1<<i)]*=f[j],g[j^(1<<i)]*=g[j];
        for(int i=0;i<m;i++) f[i]*=q[pc(i)],g[i]*=p[pc(i)];
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)
            if(j>>i&1) f[j]+=f[j^(1<<i)];
        for(int i=0;i<m;i++) f[i]*=f[i];
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)
            if(j>>i&1) f[j]+=R(f[j^(1<<i)]);
        for(int i=0;i<m;i++)
        {
            f[i]*=g[i];
            if(!f[i].fi) ad(ans,f[i].se);
        }
        cout<<ans<<"\n";
    }
    return 0;
}