去不了 NOI 的菜雞終于把集合看懂了，寫個博客加深一下印象。
[NOI2025] 集合

要求：

先處理這題比較特殊的 \([f(p)=f(Q)]\)，考慮枚舉 \(f(P)=f(Q)=S\)。\(f(P),f(Q)\) 恰好等于 \(S\) 不好做，容斥一下變成包含：

發現容斥系數上的 \(-2|S|\) 沒有用，可以去掉，所以也就沒有必要枚舉 \(S\)，只需要枚舉 \(T_P,T_Q\) 然后乘上合法的 \(S\) 數量即可，而合法的 \(S\) 滿足 \(S\subseteq T_P,T_Q\) 也即 \(S\subseteq T_P\cap T_Q\)，所以合法的 \(S\) 數量為 \(2^{|T_P\cap T_Q|}\)。為了美觀，下面用 \(S,T\) 分別代替 \(T_P,T_Q\)。

\(S \subseteq f(P)\) 相當于什么，其實就是說 \(P\) 中的數都要是 \(S\) 的超集，我們設 \(R_S\) 為 \(S\) 的超集構成的集合，則 \(P\subseteq R_S\)，于是我們就把跟 \(f\) 有關的東西去掉了。
然后處理 \([P\cap Q = \emptyset]\)，我們直接去枚舉 \(R=P\cup Q\)，顯然 \(R\subseteq R_S\cup R_T\)。那么對于 \(i\in R\)，若 \(i\) 只屬于 \(R_S\) 和 \(R_T\) 中的一個，則 \(i\) 只能放到那一個，否則 \(i\) 放到哪一個都可以。

設 \(f_S=\prod_{i\in R_S} (a_i+1),g_S=\prod_{i\in R_S} (2a_i+1)\)，這兩個可以高維后綴積 \(O(n2^n)\) 預處理。又發現 \(R_S\cap R_T=R_{S\cup T}\)：

然后這里有個問題是分母可能為 \(0\)，有一個 trick 是直接把每個數用 \(x\times 0^k\) 的形式存儲，表示這個數里面目前有 \(k\) 個 \(0\)，然后就可以做除法了。
發現這個式子里同時有 \(S\cap T\) 和 \(S\cup T\)，但是 \(S\cap T\) 我們只關心他的大小，所以我們可以用 \(|S\cap T|=|S|+|T|-|S\cup T|\) 來換掉：

設 \(F(S)=(-2)^{|S|}f(S),h=F\times F\)，這里 \(\times\) 是或卷積，則：

最后一個問題是，這里 \(F\) 是用 \(x\times 0^k\) 的形式存儲，但是做 FMT 的時候涉及到加減法，當 \(k_1\ne k_2\) 時，兩個數 \(x1\times 0^{k_1},x2\times 0^{k_2}\) 無法簡單的加減法。
不過注意到我們在除以 \(f(S)^2\) 之后不可能除出來一個 \(0\) 的負次冪，所以對于分子中 \(0\) 的非最低次項他除完分母之后 \(0\) 的冪一定 \(>0\)，所以貢獻一定為 \(0\)，因此在做加減法的時候直接舍棄次冪大的那個即可。

code

#include<bits/stdc++.h>
#define Debug puts("-------------------------")
using namespace std;
const int N=(1<<20)+5,mod=998244353,inv2=(mod+1)/2;

inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
	return w*s;
}
int c,T,n,a[N],p[30],p2[30];
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=1ll*ans*a%mod;
		b>>=1,a=1ll*a*a%mod;
	}
	return ans;
}
struct Val{
	int x,k;
	Val() : x(0),k(0) {}
	Val(int _x,int _k) : x(_x),k(_k) {}
}f[N],g[N],h[N],F[N]; 
Val operator * (const Val &u,const Val &v){return Val(1ll*u.x*v.x%mod,u.k+v.k);}
Val operator + (const Val &u,const Val &v){
	if(u.k==v.k) return Val((u.x+v.x)%mod,u.k);
	return u.k<v.k?u:v;
}
Val operator - (const Val &u,const Val &v){
	if(u.k==v.k) return Val((u.x-v.x+mod)%mod,u.k);
	return u.k<v.k?u:v;
}
void OR(Val *a,int t){
	for(int i=1;i<(1<<n);i<<=1){
		for(int len=i<<1,j=0;j<(1<<n);j+=len){
			for(int k=0;k<i;k++){
				if(t==1) a[j+k+i]=a[j+k+i]+a[j+k];
				else a[j+k+i]=a[j+k+i]-a[j+k];
			}
		}
	}
}	
signed main(){
	p[0]=p2[0]=1;
	for(int i=1;i<=25;i++) p[i]=(mod-2*p[i-1]%mod)%mod,p2[i]=1ll*p2[i-1]*inv2%mod;
	c=read(),T=read();
	while(T--){
		n=read();
		for(int i=0;i<(1<<n);i++){
			a[i]=read();
			f[i]=(a[i]+1==mod)?Val(1,1):Val(a[i]+1,0);
			g[i]=(2*a[i]+1==mod)?Val(1,1):Val((2*a[i]+1)%mod,0);
		}
		for(int i=0;i<n;i++){
			for(int s=0;s<(1<<n);s++){
				if(!(s>>i&1)) f[s]=f[s]*f[s|(1<<i)],g[s]=g[s]*g[s|(1<<i)];
			}
		}
		for(int s=0;s<(1<<n);s++) F[s]=Val(1ll*f[s].x*p[__builtin_popcount(s)]%mod,f[s].k);
		OR(F,1);
		for(int s=0;s<(1<<n);s++) h[s]=F[s]*F[s];
		OR(h,-1);
		int ans=0;
		for(int s=0;s<(1<<n);s++){
			Val t1=h[s]*g[s],t2=f[s]*f[s];
			if(t1.k==t2.k) (ans+=1ll*t1.x*qp(t2.x,mod-2)%mod*p2[__builtin_popcount(s)]%mod)%=mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}