专栏文章

题解：P13275 [NOI 2025] 集合

IIvanZhang2009
P13275题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miovbx4l
此快照首次捕获于
2025/12/03 01:45
3 个月前
此快照最后确认于
2025/12/03 01:45
3 个月前
查看原文
赛时完全不知道怎么做，把三方暴力 dp 的 O(8n)O(8^n) 卡过了 n≤10n\le 10 带多测，然后最后一个小时才看出来有用的容斥，喜提没做完。
考虑这个特殊性质 B，大概就是让你把系数凑成 ai+1a_i+1 状物。但是完全不知道怎么凑啊？它看上去就像是一个选一个或者不选的组合意义。
考虑随机找个方向容斥。第一个想法是对着 P∩QP\cap Q 容斥，但是我场上浪费了两个小时毫无进展。
记 f(P)f(P) 为 PP 中元素与和，w(P)w(P) 为 PP 中元素 aia_i 乘积。对于整数 x∈[0,2n)x\in[0,2^n)，记 xix_i 为 ⌊x2i⌋ mod 2\lfloor\frac{x}{2^i}\rfloor\bmod 2，即二进制下第 ii 位。
考虑尝试对着 f(P)=f(Q)f(P)=f(Q) 容斥。一个无敌的想法是考虑 A=f(P)−f(Q),B=f(Q)−f(P)A=f(P)-f(Q),B=f(Q)-f(P)（这里的减法视作集合减法，即 S−TS-T 中存在元素 xx 当且仅当 SS 中存在 TT 中不存在，此处即 AA 表示 f(P)i=1,f(Q)i=0f(P)_i=1,f(Q)_i=0 的 ii 的集合，BB 同理）。
我们直接容斥 AA 和 BB！枚举 A,BA,B，容斥系数 (−1)∣A∣+∣B∣(-1)^{\mid A\mid+\mid B\mid}，表示对于 AA 中的位，要求 PP 所有数在这一位不含 00，QQ 至少存在一个这一位是 00 的；对于 BB 中的位，要求 QQ 所有数在这一位不含 00，PP 至少存在一个这一位是 00 的。
考虑对于“至少存在一个”继续容斥。枚举 C⊂A,D⊂BC\subset A,D\subset B 表示容斥：对于 CC 中的位，QQ 这一位不含 00（本来是 AA 中的位 QQ 这一位得存在一个 00，枚举子集钦定不成立的容斥）；对于 DD 中的位，PP 这一位不含 00。容斥系数 (−1)∣C∣+∣D∣(-1)^{\mid C\mid+\mid D\mid}。这里的限制变成对于 A∪DA\cup D 的位，PP 这一位没 00；B∪CB\cup C 的位，QQ 这一位没 00。
写出来相当于：
∑C⊂A,D⊂B,A∩B=∅∑(A∪D)∈f(P)∑(B∪C)∈f(Q)[P∩Q=∅]w(P)w(Q)\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∈ba\in b 表示二进制下 aa 是 bb 的子集。
假设你以及枚举了 A,B,C,DA,B,C,D，考虑一个数 ii 可以放在哪里（三种选择，放 PP，放 QQ，都不放）。如果 (A∪D∪B∪C)∈i(A\cup D\cup B\cup C)\in i，则显然贡献是 2ai+12a_i+1；如果上述不满足，且满足 (A∪D)∈i(A\cup D)\in i 或 (B∪C)∈i(B\cup C)\in i，则贡献是 ai+1a_i+1；否则贡献是 11。
这里“如果上述不满足”的限制比较唐。在性质 B 中 ai≠−1a_i\neq -1，也就是说 ai+1a_i+1 存在逆元。记 g(s)g(s) 表示 ∏s∈i(ai+1)\prod_{s\in i}(a_i+1)，h(s)h(s) 表示 ∏s∈i2ai+1ai+1\prod_{s\in i}\frac{2a_i+1}{a_i+1}，则贡献可以写为 h(A∪B∪C∪D)g(A∪D)g(B∪C)h(A\cup B\cup C\cup D)g(A\cup D)g(B\cup C)。
预处理 g,hg,h 可以简单高维后缀积，O(2nn)O(2^nn)。然后暴力做是枚举 A,B,C,DA,B,C,D，这里分析一下每一位是 11 的可能是：A,AC,B,BD,∅A,AC,B,BD,\empty，所以复杂度是 O(5n)O(5^n)。
考虑优化也很容易，如果先枚举 A,BA,B，则 C,DC,D 是独立的，复杂度 O(4n)O(4^n)。
如果先枚举 A,DA,D，然后高维前缀和预处理对于每一组 (A,B)(A,B) 的 DD 的贡献和，则复杂度 O(3nn)O(3^nn)。考场上止步于此了，啊啊啊。
注意到人类智慧。我们的贡献只和 A∪DA\cup D 和 B∪CB\cup C 有关。如果枚举这两个，那唯一的问题就是如何处理 A∩B=∅A\cap B=\empty？可以发现 A∩BA\cap B 的部分一定属于 (A∪D)∩(B∪C)(A\cup D)\cap(B\cup C)。而这里的每一位都可以划给 ADAD 和 BCBC，所以竟然直接乘上一个 2∣(A∪D)∩(B∪C)∣2^{\mid (A\cup D)\cap(B\cup C)\mid} 就好了！！！
记 s=A∪D,t=B∪Cs=A\cup D,t=B\cup C。重写一下式子：
∑s,t(−2)∣s∣+∣t∣2−∣S∪T∣g(s)g(t)h(s∪t)\sum_{s,t}(-2)^{\mid s\mid+\mid t\mid}2^{-|S\cup T|}g(s)g(t)h(s\cup t)
注意到 s,ts,t 独立，我们直接做或卷积，所以做到了 O(2nn)O(2^nn)。
但是这里 hh 的定义有逆元，但是逆元不一定存在，只能通过性质 B。那咋办。
其实很好做，我们用 a×Mba\times M^b 的形式存储一个数，其中 MM 是模数。注意到我们只需要做加减乘除。加法的时候令 bb 为两个里的小的那个，乘除的时候把 aa 乘起来，bb 加起来就好了。
这种题代码都很好写。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...