互异关系容斥&集合幂级数小记

最近碰见了一些互异关系容斥的题目，而这类题目往往要配合集合幂级数的一些技术使用，所以简单记记。

内容很杂，行文很乱，作者水平很低，酌情观看。

互异关系容斥

思想其实很基本，应用范围其实很广。

原论文。

思想就是对于 \(x_i\neq x_j\) 这样的限制，经典对于限制的子集容斥是钦定违反 \(S\) 中的限制，容斥系数为 \((-1)^{|S|}\)。

那么违反 \(x_i\neq x_j\) 相当于 \(x_i=x_j\)，这是一个相等关系，可以将图划分成若干个等价类进行考虑。

互异关系容斥的第一个思想便是：对于每一个等价类，求出它边集的容斥系数之和。

举个例子，假设我们现在对一张完全图 \(K_n\) 的边集施加了容斥。这样相当于这张图被划分成了若干个等价类。对于大小为 \(m\) 的等价类，我们实际上要求的是所有使等价类联通的边集 \(E\subseteq E_{K_m}\) 的 \((-1)^{|E|}\) 之和。

设 \(f_n=\sum_{E\subseteq E_{K_n}} (-1)^{|E|}=[n=1]\)，求个 \(\ln\) 就是联通图的系数：

\[g_n=f_n-\sum_{i=1}^n {n-1 \choose i-1} g_i f_{n-i}
\]

归纳知：\(g_n=(-1)^{n-1} (n-1)!\)。

互异关系容斥的第二个思想就是：对于 \(\bigoplus_{i=1}^n x_i=c\) 这样一种限制，如果 \(x_i\) 关于 \(\oplus\) 运算逆元总是存在且唯一（如模素数的加法群），那么我们如果知道了 \(x_1,x_2\dots x_{n-1}\) 就可以唯一确定一个 \(x_n\)。

那么如果不限制 \(x_i\) 互不相同，满足上述限制的个数就是 \(V^{n-1}\)，\(V\) 是 \(x_i\) 的值域大小。

限制 \(x_i\) 互不相同可以看看周子衡大佬的论文是如何解决的。

集合幂级数

了解甚浅……只会一些基本的应用。

首先 \(\text{FWT}\) 应用了线性变换关于各维独立的性质，相当于给每一维乘上了一个 \(2\times 2\) 的矩阵。

我们不仅要知道 \(\text{FWT}\) 对于每一维分别的影响，更要知道做完 \(\text{FWT}\) 后整体的结果是怎样的。

具体地：

\[\text{or-FWT}：g_S=\sum_{T\subseteq S} f_T\\
\text{or-IFWT}：g_S=\sum_{T\subseteq S} (-1)^{|S|-|T|} f_T\\
\text{and-FWT}：g_S=\sum_{S\subseteq T} f_T\\
\text{and-IFWT}：g_S=\sum_{S\subseteq T} (-1)^{|S|-|T|} f_T\\
\text{xor-FWT}：g_S=\sum_{S\subseteq T} (-1)^{|S \cap T|} f_T\\
\text{xor-IFWT}：g_S=\frac{1}{2^n}\sum_{S\subseteq T} (-1)^{|S \cap T|} f_T\\
\]

然后子集卷积定义了 \(n+1\) 个占位幂级数。我们对占位幂级数 \(\text{or-FWT}\) 后的结果可以上各种各样的多项式操作。这里的操作由于都不是复杂度瓶颈所以都可以 \(O(n^2)\) 递推。

\(\ln:g_n=f_n-\frac{1}{n}\sum_{i=1}^{n-1} g_i i f_{n-i}\)。需要保证常数项为 \(1\)。

\(\exp:g_n=\frac{1}{n}\sum_{i=1}^{n} f_i i g_{n-i}\)。需要保证常数项为 \(0\)。

\(\mathrm{inv}:g_n=\frac{1-\sum_{i=0}^{n-1} g_i f_{n-i}}{f_0}\)。需要保证常数项存在逆。

注意！对于 \(F^n\) 不要多项式 \(\ln\) 再 \(\exp\)，可以直接递推：

\[G=F^n\Rightarrow G'=nF^{n-1} F' \Rightarrow FG'=nF^n F'\Rightarrow FG'=nGF'
\]

比较系数即可递推。\(n\) 可以是有理数，顺便实现了多项式开根。

[HNOI2011] 卡农

求从 \(1,2,3\dots 2^k-1\) 中选 \(n\) 个数满足异或和为 \(0\) 的方案数。

递推做法前人之述备矣。我们考虑上点科技。

做法一：互异关系容斥

具体参考原论文。

原论文里给的第二道例题允许空集。这里要求不含空集，我们可以上点容斥，利用递推/推式子容斥掉空集。

不过这样做感觉有点复杂？还不如直接递推。

做法二：集合幂级数

发现如果定义形式幂级数乘法为异或卷积，答案就是：\(\prod_{S\neq \emptyset}(1+x^S y)\) 的 \(y^n\) 项系数。

我们对于每一个式子手动 \(\text{xor-FWT}\) 后点乘起来然后手动 \(\text{xor-IFWT}\)。

具体参见 qwaszx 题解。

QOJ 5827 异或图

给定一张图，\(\forall (u,v)\in E,b_u\neq b_v\)，\(b_i\in [1,a_i]\)，求 \(\mathrm{xor}_{i=1}^n b_i=c\) 的方案数。\(n\leq 15\)。

如果没有互异关系，那么可以直接数位 \(\text{DP}\)。具体地，如果有一位上界是 \(1\) 但填了 \(0\) 那么后面的位任选，相当于去掉了异或和的限制，可以直接算方案数。

现在对互异关系上容斥，求出每一个点子集的容斥系数，集合幂级数求个 \(\ln\) 就得到了点子集是连通块的容斥系数。

发现大小为奇数的连通块相当于替换成一个数的限制 \(\min_{i\in S} a_i\)，偶数连通块直接给答案乘上 \(\min_{i\in S} a_i + 1\)。

于是设 \(f_{S,T}\) 表示奇数联通块的限制下标为 \(T\)，\(\text{DP}\) 即可。

复杂度上界是 \(O(4^n)\)，但跑不满，然而写 unordered_map 会被卡常，用 vector 存一下就可以了。

#include <cstdio>

#include <vector>

using namespace std;

template<typename T>

T read(){

	char c=getchar();T x=0;

	while(c<48||c>57) c=getchar();

	do x=(x<<1)+(x<<3)+(c^48),c=getchar();

	while(c>=48&&c<=57);

	return x;

}

const int N=33,S=1<<15,LG=63,P=998244353;

typedef long long ll;

int n,m,rk;ll c;

ll a[N],lis[N];

bool ban[S];

int coe[S],pos[S];

void inc(int &x,int v){if((x+=v)>=P) x-=P;}

void dec(int &x,int v){if((x-=v)<0) x+=P;}

vector< pair<int,int> > f[S];

int tmp[S];

int suf[N][2];

bool sta[LG],vis[S];

int stk[S],tp;

void upd(int x,int val){

	if(!vis[x]) vis[stk[tp++]=x]=1;

	inc(tmp[x],val);

}

int main(){

	n=read<int>();m=read<int>();c=read<ll>();

	for(int i=0;i<n;++i) a[i]=read<ll>();

	for(int i=0;i<m;++i){

		int u=read<int>()-1,v=read<int>()-1;

		ban[(1<<u)|(1<<v)]=1;

	}

	for(int i=1;i<(1<<n);i<<=1)

		for(int j=0;j<(1<<n);j+=(i<<1))

			for(int k=j;k<(j|i);++k) ban[k|i]|=ban[k];

	for(int s=1;s<(1<<n);++s){

		int lb=__builtin_ctz(s);

		int _s=s^(1<<lb);

		pos[s]=lb;

		if(_s&&a[pos[_s]]<a[lb]) pos[s]=pos[_s];

		coe[s]=!ban[s];

		for(int _t=_s;;_t=(_t-1)&_s){

			int t=_t|(1<<lb);

			if(t!=s&&!ban[s^t]) dec(coe[s],coe[t]);

			if(!_t) break;

		}

	}

	f[0].emplace_back(0,1);

	for(int s=1;s<(1<<n);++s){

		int lb=__builtin_ctz(s);

		int _s=s^(1<<lb);

		tp=0;

		for(int _t=_s;;_t=(_t-1)&_s){

			int t=_t|(1<<lb);

			for(auto [x,val]:f[s^t])

				if(__builtin_parity(t)) upd(x|(1<<pos[t]),(ll)coe[t]*val%P);

				else upd(x,(a[pos[t]]+1)%P*val%P*coe[t]%P);

			if(!_t) break;

		}

		f[s].resize(tp);

		for(int i=0;i<tp;++i){

			int x=stk[i];

			f[s][i]=make_pair(x,tmp[x]);

			tmp[x]=0;vis[x]=0;

		}

	}

	int res=0;

	for(auto [s,val]:f[(1<<n)-1]){

		rk=0;

		for(int i=0;i<n;++i)

			if(s>>i&1) lis[rk++]=a[i];

		int ans=0;

		for(int t=59;~t;--t){

			suf[rk][0]=1;suf[rk][1]=0;

			for(int i=rk-1;~i;--i){

				sta[i]=lis[i]>>t&1;

				if(sta[i]){

					lis[i]^=(1ll<<t);

					suf[i][0]=((1ll<<t)%P*suf[i+1][0]+(lis[i]+1)%P*suf[i+1][1])%P;

					suf[i][1]=((1ll<<t)%P*suf[i+1][1]+(lis[i]+1)%P*suf[i+1][0])%P;

				}

				else{

					suf[i][0]=(lis[i]+1)%P*suf[i+1][0]%P;

					suf[i][1]=(lis[i]+1)%P*suf[i+1][1]%P;

				}

			}

			int par=(c>>t&1),cur=1;

			for(int i=0;i<rk;++i){

				if(sta[i]){

					ans=(ans+(ll)cur*suf[i+1][par])%P;

					par^=1;

				}

				cur=(lis[i]+1)%P*cur%P;

			}

			if(par) break;

			if(!t) ++ans;

		}

		res=(res+(ll)ans*val)%P;

	}

	printf("%d\n",res);

	return 0;

}

互异关系容斥&集合幂级数小记的相关教程结束。