也许更好的阅读体验

定义

集合幂级数

为了更方便的研究集合的卷积，引入集合幂级数的概念
集合幂级数也是形式幂级数的一种，只是集合的一种表现形式，无需考虑收敛或发散的含义

定义一个集合 $S$S 的集合幂级数为 $f$f ，那么我们就可以把集合 $S$S 表示为如下形式

$\begin{array}{c}{\displaystyle f=\sum _{T\subseteq S}{f}_T\cdot x^T}\end{array}$f=T⊆S∑​fT​⋅xT​
$f_T$fT​为 $T$T这个集合幂级数的系数
简单来说就是用二进制表示集合的元素是否存在，并将其写成多项式的形式

约定

$c=(a,b)$c=(a,b)表示将 $a,b$a,b连起来组成 $c$c
为了方便，将 $f\ast g$f∗g写成 $fg$fg

卷积运算

加法

$\begin{array}{c}{\displaystyle h=f+g}\end{array}$h=f+g​
那么
$h_S=f_S+g_S$hS​=fS​+gS​

减法

$\begin{array}{c}{\displaystyle h=f-g}\end{array}$h=f−g​
那么
$h_S=f_S-g_S$hS​=fS​−gS​

乘法

$\begin{array}{c}{\displaystyle h=f\ast g}\end{array}$h=f∗g​
那么
$\begin{array}{c}{\displaystyle h_S=\sum _{i\circ j\subseteq S}{f}_i{g}_j}\end{array}$hS​=i∘j⊆S∑​fi​gj​​
其中 $\circ$∘可以是与，或，异或运算

集合并卷积 就是 $\circ$∘进行或运算
子集卷积 就是 $\circ$∘进行与运算
集合对称差卷积 就是 $\circ$∘进行异或运算

快速求法

加法和减法都可以在 $O\left(n\right)$O(n)时间复杂度内求出结果
对乘法，有一些优化的算法，以集合并卷积为例

分治

设 $f$f有 $2^n$2n项
考虑将其集合幂级数的第 $n$n个元素提出来
则 $f=f^{-}+x^{\left\{n\right\}}{f}^{+}$f=f−+x{n}f+，可以知道 $f^{-}$f−为前 $2^{n-1}$2n−1项， $f^{+}$f+为后 $2^{n-1}$2n−1项即 $f^{-}$f−的第 $n$n个元素在二进制下为 $0$0， $f^{+}$f+的第 $n$n个元素在二进制下为 $1$1
$\begin{array}{cc}{\displaystyle fg}& {\displaystyle =(f^{-}+x^{\left\{n\right\}}{f}^{+})(g^{-}+x^{\left\{n\right\}}{g}^{+})}\\ {\displaystyle }& {\displaystyle =f^{-}{g}^{-}+x^{\left\{n\right\}}(f^{-}{g}^{+}+f^{+}{g}^{-}+f^{+}{g}^{+})}\\ {\displaystyle }& {\displaystyle =f^{-}{g}^{-}+x^{\left\{n\right\}}((f^{-}+f^{+})(g^{-}+g^{+})-f^{-}{g}^{-})}\end{array}$fg​=(f−+x{n}f+)(g−+x{n}g+)=f−g−+x{n}(f−g++f+g−+f+g+)=f−g−+x{n}((f−+f+)(g−+g+)−f−g−)​
这样计算 $fg$fg就只要计算 $f^{-}{g}^{-}$f−g−和 $(f^{-}+f^{+})(g^{-}+g^{+})$(f−+f+)(g−+g+)了
此时已经没有 $n$n这个元素了，因为
于是我们可以递归分治求解 $fg$fg
时间复杂度 $O\left(n{2}^n\right)$O(n2n)

$Code$Code

void fold (int *f,int *g,int *h,int hlen)//hlen -> half len
{
	if (hlen==1)	return void(h[0]=f[0]*g[0]);
	for (int i=0;i<hlen;++i)	f[i+hlen]+=f[i],g[i+hlen]+=g[i];
	fold(f,g,h,hlen>>1),fold(g+hlen,g+hlen,h+hlen,hlen>>1);
	for (int i=0;i<hlen;++i)	f[i+hlen]-=f[i],g[i+hlen]-=g[i];
}

快速莫比乌斯变换(FMT)

对于一个集合幂级数 $f$f，我们定义其快速莫比乌斯变换为集合幂级数 $\widehat{f}$f ​,使其系数满足
$\begin{array}{c}{\displaystyle {\widehat{f}}_S=\sum _{T\subseteq S}{f}_T}\end{array}$f ​S​=T⊆S∑​fT​​

由容斥原理，我们可以得到
$\begin{array}{c}{\displaystyle f_S=\sum _{T\subseteq S}{(-1)}^{\mid S\mid -\mid T\mid }{\widehat{f}}_T}\end{array}$fS​=T⊆S∑​(−1)∣S∣−∣T∣f ​T​​

考虑乘法 $\widehat{h}=\widehat{f}\widehat{g}$h =f ​g ​
$\begin{array}{cc}{\displaystyle {\widehat{h}}_s}& {\displaystyle =\sum _{i\subseteq S}\sum _{j\subseteq S}{f}_i{g}_j}\\ {\displaystyle }& {\displaystyle =\left(\sum _{i\subseteq S}{f}_i\right)\left(\sum _{j\subseteq S}{g}_j\right)}\\ {\displaystyle }& {\displaystyle ={\widehat{f}}_S{\widehat{g}}_S}\end{array}$h s​​=i⊆S∑​j⊆S∑​fi​gj​=(i⊆S∑​fi​)⎝⎛​j⊆S∑​gj​⎠⎞​=f ​S​g ​S​​

那么，现在我们知道想办法怎么求 $\widehat{f}$f ​和 $\widehat{g}$g ​，然后把它们的系数乘起来，就可以得到 $\widehat{h}$h
然后再将其反演得到 $f$f(因为容斥是肯定会超时的)

考虑递推
我们设 ${\widehat{f}}_S^{\left(i\right)}$f ​S(i)​使其满足
$\begin{array}{c}{\displaystyle {\widehat{f}}_S^{\left(i\right)}=\sum _{T\subseteq S}[(S-T)\subseteq \{1,2,\dots ,i\}]f_T}\end{array}$f ​S(i)​=T⊆S∑​[(S−T)⊆{1,2,…,i}]fT​​
即若 $i+1\sim n$i+1∼n有元素属于 $S$S，则必须要选择，而 $1\sim i$1∼i中的元素可有可无
那么我们最终的 ${\widehat{f}}_S={\widehat{f}}_S^{\left(n\right)}$f ​S​=f ​S(n)​，所有的元素都是可有可无的，即它的子集都被包含在内了
考虑第 $S$S中有没有 $i$i这个元素

• 没有，则 ${\widehat{f}}_S^{\left(i\right)}={\widehat{f}}_S^{(i-1)}$f ​S(i)​=f ​S(i−1)​
• 有，那么 ${\widehat{f}}_S^{\left(i\right)}={\widehat{f}}_S^{(i-1)}+{\widehat{f}}_{S-i}^{(i-1)}$f ​S(i)​=f ​S(i−1)​+f ​S−i(i−1)​， $S-i$S−i表示从 $S$S这个集合中去掉 $i$i这个元素，这个式子的后两项前者是第 $i$i个元素一定被选了，后者则是第 $i$i个元素一定没有被选

而要将其反演，我们考虑其逆过程，只需将所有加上来的全部减去即可

时间复杂度 $O\left(n{2}^n\right)$O(n2n)

$Code$Code

上面做法都是二维数组
考虑先枚举 $i$i再算所有 $S$S的答案，只需一维数组即可

void FMT (int *a,int n)//n个元素
{
	int all=1<<n;
	for (int i=0;i<n;++i)
		for (int j=0;j<all;++j)
			if (j>>1&1)	a[j]+=a[j^(1<<i)];
}

void IFMT (int *a,int n)//n个元素
{
	int all=1<<n;
	for (int i=0;i<n;++i)
		for (int j=0;j<all;++j)
			if (j>>i&1)	a[j]-=a[j^(1<<i)];
}

快速沃尔什变换(FWT)

我们发现，在进行分治算法中，只需保留出 $f^{-},g^{-}$f−,g−， $(f^{-}+f^{+}),(g^{-}+g^{+})$(f−+f+),(g−+g+)就可以算出答案了
可惜递归的常数相对来说太大，我们考虑将其写成循环的形式就可以得到 $FWT$FWT了

若不考虑分治写成循环，我们换一种方法理解 $FWT$FWT，当然，这是另一种思路了，上面将递归改成循环的思路是正确的
上面的 $f=f^{-}+f^{+}$f=f−+f+，我们是始终让其满足这个条件的，所以在后面还减去了一个 $f^{-}{g}^{-}$f−g−
让我们跳出思维的局限，弄这么一个 $f^{\prime },g^{\prime }$f′,g′使其满足 $(fg{)}^{\prime }=f^{\prime }{g}^{\prime }$(fg)′=f′g′，这样我们只要计算 $f^{\prime }{g}^{\prime }$f′g′，然后把它反演一下就可以得到 $fg$fg
这里呢
$f^{\prime }=(f^{-},f^{-}+f^{+})$f′=(f−,f−+f+)
为什么这样就可以呢
考虑 $(fg{)}^{\prime }$(fg)′，根据上面的推导
${\left(fg\right)}^{\prime }=(f^{-}{g}^{-},(f^{-}+f^{+})(g^{-}+g^{+}))$(fg)′=(f−g−,(f−+f+)(g−+g+))
再考虑 $f^{\prime }{g}^{\prime }$f′g′
$f^{\prime -}{g}^{\prime -}=f^{-}{g}^{-}$f′−g′−=f−g−
$f^{\prime +}{g}^{\prime +}=(f^{-}+f^{+})(g^{-}+g^{+})$f′+g′+=(f−+f+)(g−+g+)
所以这样是可以的
于是我们可以得到
$f^{\prime }=(f^{-},f^{-}+f^{+})$f′=(f−,f−+f+)
然后称这样的 $f^{\prime }$f′叫做沃尔什变换
$FWT\left(f\right)=FWT(f^{-},f^{-}+f^{+})$FWT(f)=FWT(f−,f−+f+)

反演也很简单
即将多算的 $f^{-}$f−减去即可

$Code$Code

void FWT (int *a,int n)
{
	for (int len=2;len<=n;len<<=1)
		for (int i=0,hlen=len>>1;i<n;i+=len)
			for (int j=i,k=j+hlen;j<k;++j)
				a[j+hlen]+=a[j];
}

void IFWT (int *a,int n)
{
	for (int len=2;len<=n;len<<=1)
		for (int i=0,hlen=len>>1;i<n;i+=len)
			for (int j=i,k=j+hlen;j<k;++j)
				a[j+hlen]-=a[j];
}

时间复杂度 $O\left(n{2}^n\right)$O(n2n)

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
如能得到推荐博主就更开心了
您的鼓励是博主的动力