快速莫比乌斯变换&子集卷积

快速莫比乌斯变换(FMT)可以方便地解决子集交卷积子集并卷积,形式化地讲就是求一个$\rm C$:
$$
c_i=\sum_{k\cup j=i} a_kb_j\\\
c_i=\sum_{k\cap j=i} a_kb_j
$$
快速子集变换(FST)则是在FMT基础上的扩展,解决的也是子集交卷积,但是限制了状态不重复,即
$$
c_i=\sum_{\substack{~k\cup j=i\\ k \cap j= \emptyset }}a_kb_j
$$
换个写法:
$$
c_s=\sum_{t\subseteq s}a_sb_{s-t}
$$
同时,以上两种变换所涉及的交集、并集和差集的对象都是集合(也就是$c_i$的下角标$i$指代的是集合),其二进制表示能更好地展示这一点。

$\rm{FMT}$

首先我们考虑一步线性变换的实质。考虑FFT,其本质是通过DFT使得我们可以直接线性地逐项相乘,即
$$
\begin{aligned}
\rm {C} & =\rm{A*B}\\\
\Longrightarrow \rm{DFT(C)_i} & =\rm{DFT(A)_i\cdot DFT(B)_i}
\end{aligned}
$$
那么我们同时也希望构造出一种变换使得可以逐项相乘。

$(1)$ 子集并卷积

不妨先扩大一下范围,即若$A\cup B=C$,则一定有$A\subseteq C$且$B \subseteq C$,但是反过来不一定。

那么先考虑$\rm MT$,即考虑一种变换而不思考其复杂度。我们令
$$
\rm MT(F)_i= \mathcal{\sum_{j\subseteq i} f_j}
$$
则有
$$
\rm{MT(F)_i\cdot MT(G)_i}=\mathcal{\sum _{j,k\subseteq i} f_j\cdot g_k}
$$
而实际上我们求的是
$$
\rm{P_i}=\mathcal{\sum_{j\cup k=i}f_jg_k}
$$
而我们发现
$$
\begin{aligned}
\sum _{j\subseteq i}{\rm}_j &=\sum_{d \subseteq i} \sum_{j\cup k=d}f_jg_k\\ &= \sum_{j,k\subseteq i} f_jg_k\\ &= \rm{MT(P)_i}\end{aligned}
$$
也就是说有
$$
\rm MT(F)_i\cdot MT(G)_i =MT(P)_i
$$
于是就构造出了这样的线性变换,本质就是子集和。

但是普通的子集和是$O(2^nn)$的,但是我们的$n$是$100000$级别,所以考虑一个dp一样的东西。就是我们每次枚举每一位,那么这一位为0就是这一位为1的子集,所以类加进答案。于是这样的复杂度就变成了$n\log n$

1
2
3
4
5
6
7
//N = (1 << M) - 1 ;
void fmt_or(int *f, int g){
int i, j ;
for (i = 0 ; i < N ; ++ i)
for (j = 0 ; j <= M ; ++ j)
if (j >> i & 1) f[j] = (Mod + f[j] + 1ll * g * f[j ^ (1 << i)]) % Mod ;
}

$(2)$ 子集交卷积

我们对称思考,即令$\rm{MOT}$表示交卷积的变换,那么应该有:
$$
\rm MOT(F)_i= \mathcal{\sum_{i\subseteq j} f_j}
$$
那么
$$
\rm{MOT(F)_i\cdot MOT(G)_i}=\mathcal{\sum _{i\subseteq j,i\subseteq k} f_j\cdot g_k}
$$
我们要求的是
$$
\rm{Q_i}=\mathcal{\sum_{j\cap k=i}f_jg_k}
$$
则:
$$
\begin{aligned}
\sum _{i\subseteq j}{\rm}_j &=\sum_{i \subseteq d} \sum_{j\cap k=d}f_jg_k\\ &= \sum_{i\subseteq j,i\subseteq k} f_jg_k\\ &= {\rm{MOT(Q)}_i}\end{aligned}
$$
于是就直接反着求一遍即可。

然后这东西就也还是个dp,复杂度$n \log n$

1
2
3
4
5
6
void fmt_and(int *f, int g){
int i, j ;
for (i = 0 ; i < N ; ++ i)
for (j = M ; j >= 0 ; -- j)
if (~j >> i & 1) f[j] = (Mod + f[j] + 1ll * g * f[j | (1 << i)]) % Mod ;
}

$(3)$ 优化:增量分治

阅读提示:优你🐎的化,这就是个FWT。

以下是以前的翻车现场:


实际上我觉得也没怎么优化……

拿并卷积举例,大体上就是我们考虑如果存在$i\subseteq j\subseteq k$,我们朴素的要算两次,但实际上我们对于前半部分的$k$只需要算一次。这样实际上就是我们考虑每次只转移前$n-i$个元素相同的集合。

(以下内容来自Rockdu的$blog$)

于是每当多了一个元素,即我们考虑由$i$层转移到$i+1$层,发现只是多了一个元素的状态——讨论一下这个元素取不取,发现这个元素不取,答案就和原来一样,因为它的子集和不变;如果这个元素要取,那么这个元素不取的情况是它的子集,会多出这个元素不取的子集和。最终我们发现,到第$i$层只需要把第$i$个元素不取的状态加到第$i$个元素取的状态就可以了。

于是代码:

1
2
3
4
5
6
void FMT(int * A, int n, int t) {
for(int i = 1; i < (1 << n); i <<= 1)
for(int p = i << 1, j = 0; j < (1 << n); j += p)
for(int k = 0; k < i; ++k)
(A[i + j + k] += A[j + k]) %= Mod ;
}

看上去每次只用计算一半,但是JOHNKRAM神仙是这么说的:

你看他长得和FFT的蝴蝶操作一毛一样,所以还是$n\log n$的。


= =假酒害人,假代码更害人

$\rm FST$

这个名字不是很吉利

这东西其实也不是非要用$\rm FMT$来做,$\rm FWT$也可以。

然后就是考虑在卷积的时候多增加一维,即$f_{i,S}$表示集合$S$中有$i$个元素,于是发现只有当元素个数相加符合时才是对的。

于是一开始将$f_{bct(s),s}$赋值为$f_s$,其中$bct(s)=\rm bitcount(s)$。然后对每一个$f_i$分别做$\rm FMT$,之后按位乘的时候需要
$$
P_{i, S}=\sum_{i=0}^{i} f_{j, S} * g_{i-j, S}
$$
输出的时候只输出$P_{bct(s),s}$即可。

板子题是LOJ #152,略微卡常,被逼无奈写了神奇的取模优化233

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <iostream>

#define MAXN 21
#define MAXM 1056701
#define Mod 1000000009

#define I inline
#define LL long long

using namespace std ; int bc[MAXM] ;
int N, M ; LL A[MAXN][MAXM], B[MAXN][MAXM], C[MAXN][MAXM] ;

I int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
I void reduce(LL &x) { x += x >> 63 & Mod ; }
I void Ifmt(LL *f){
register int i, j ;
for (i = 0 ; i < N ; ++ i)
for (j = 0 ; j <= M ; ++ j)
if (j >> i & 1) reduce(f[j] -= f[j ^ 1 << i]) ;
}
I void fmt(LL *f){
register int i, j ;
for (i = 0 ; i < N ; ++ i)
for (j = 0 ; j <= M ; ++ j)
if (j >> i & 1) reduce(f[j] += f[j ^ 1 << i] - Mod) ;
}
int main(){
cin >> N ; M = (1 << N) - 1 ; register int i, j, s ;
for (i = 1 ; i <= M ; ++ i) bc[i] = bc[i - (i & -i)] + 1 ;
for (i = 0 ; i <= M ; ++ i) A[bc[i]][i] = read() ;
for (i = 0 ; i <= M ; ++ i) B[bc[i]][i] = read() ;
for (i = 0 ; i <= N ; ++ i) fmt(A[i]), fmt(B[i]) ;
for (i = 0 ; i <= N ; ++ i)
for (j = 0 ; j <= i ; ++ j)
for (s = 0 ; s <= M ; ++ s)
(C[i][s] += A[j][s] * B[i - j][s]) %= Mod ;
for (i = 0 ; i <= N ; ++ i) Ifmt(C[i]) ;
for (i = 0 ; i <= M ; ++ i) printf("%d ", C[bc[i]][i]) ;
}

后记

实际上国际上根本不通用FMT和FST这两个简写(甚至可能国内也没几个人用FST指代”子集卷积“),于是就只能233了

upd:有些说明参见FWT的讲解。

$\rm Referance$