快速莫比乌斯变换 FMT 与 快速沃尔什变换 FWT。
1.定义
一个长度为 $2^n$ 的序列 $f(i)$，有一个生成函数 $F(x)=\sum_{i=0}^{2^n-1}f(i) x^i$，那么，这个生成函数叫做集合幂级数。
这和集合有什么关系呢？将集合 ${0,1,\cdots,n-1 }$ 的一个子集状态压缩后就对应着原序列的一个下标 $i$。
其卷积形式大多为 $c(i)=\sum_{j\oplus k=i}a(j)*b(k)$，这里的 $\oplus$ 指代某种运算，其大多是位运算。
直接暴力求卷积是 $\mathcal O(4^n)$ 的，考虑更优的做法。
2.快速莫比乌斯变换 FMT
用来求高维前缀和。高维前缀和就是对 $n$ 维数组求前缀和，不过每一维只有 $0,1$ 两个下标。本质上就是子集和 $b(i)=\sum_{j|i=i} a(j)$。暴力枚举子集来求的时间复杂度是 $\mathcal O(3^n)$ 的。
是实际上我们可以对每一维单独来做遍前缀和，容易发现这样做是正确的。于是是时间复杂度 为 $\mathcal O(n2^n)$。
其实这样做法也可以从子集和或者另外的角度来理解。而高维后缀和同理。
Code
1
2
3
4
| for(int i=0;i<n;i++)
for(int j=0;j<1<<n;j++)
if(j>>i&1)
a[j]+=a[j^(1<<i)];
|
3.快速沃尔什变换 FWT
用于求异或卷积，在下面说。
4.卷积
为了让卷积 $c(i)=\sum_{j\oplus k=i}a(i)*b(i)$ 更快计算，我们需要用 FMT/FWT 将 $a,b$ 进行变换，再 $\mathcal O(n)$ 求出变换后的 $c$，再对其进行逆变换就可以求出原本的 $c$。
1.或卷积
求卷积 $c_i=\sum_{j|k=i} a_j*b_k$。
考虑构造出变换 $FMT(c)_x=FMT(a)_x*FMT(b)_x$。
证明如下：
于是先对 $a,b$ 做一次高维前缀和，相乘后做一次逆变换即得到了 $c$。
2.与卷积
和或卷积类似，将高维前缀和变为高维后缀和即可。
3.异或卷积
求卷积 $c_i=\sum_{j\oplus k=i} a_j*b_k$。
我们设对序列 $a$ 变换为 $FWT(a)_x=\sum_{i=0}^{n-1} g(x,i)a_i$。
我们要想使
尝试变换一下：
于是得到：
我们需要构造的式子需要满足上面这个等式，并且能够快速得到 $FWT(a)$。前人的智慧告诉我们应当为 $g(x,i)=(-1)^{|i\odot x|}$，因为有 $(i\oplus j)\odot x=(i\odot x)\oplus (j\odot x)$。所以 FWT 的式子就是：
至于如何快速求出 $FWT(a)$，考虑一个类似于蝶形运算的过程，具体可见代码，这里不再赘述。这样总的时间复杂度为 $\mathcal O(n2^n)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| inline void FWT(int n,int *a)
{
int tot=1<<n;
for(int mid=1;mid<tot;mid<<=1)
for(int i=0;i<tot;i+=mid<<1)
for(int j=0;j<mid;j++)
{
int x=a[i+j],y=a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
}
}
inline void IFWT(int n,int *a)
{
int tot=1<<n;
for(int mid=1;mid<tot;mid<<=1)
for(int i=0;i<tot;i+=mid<<1)
for(int j=0;j<mid;j++)
{
int x=a[i+j],y=a[i+j+mid];
a[i+j]=x+y>>1,a[i+j+mid]=x-y>>1;
}
}
|
发现此过程和 NTT 非常相似。
4.子集卷积
求 $c_i=\sum_{j\odot k=0,j|k=i} a_j*b_k$。
注意到 $j,k$ 对 $j|k$ 有贡献，当且仅当 $\mid j\mid +\mid k\mid =\mid j|k\mid $。这启发我们按照集合的大小来进行分类。
将原序列扩展到二维为 $A_{x,i}=a_i[|i|=x]$，于是有：
这里我们同时对两边做 FMT，这显然是成立的。我们先处理出 $FMT (A_{|i|}),FMT(B_{|i|})$，求出 $FMT(C_{|x|})$ 后做 $IFMT$ 即可。时间复杂度为 $\mathcal O(n^22^n)$。
Code
1
2
3
4
5
6
7
8
9
10
| for(int i=0;i<=n;i++)
FMT(n,a[i]),FMT(n,b[i]);
for(int i=0;i<=n;i++)
for(int j=0;j<=n-i;j++)
{
for(int x=0;x<tot;x++)
c[i+j][x]=adj(c[i+j][x]+1ll*a[i][x]*b[j][x]%mod);
}
for(int i=0;i<=n;i++)
IFMT(n,c[i]);
|
5.例题
模板题。
Code
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
| #include<iostream>
#include<cstdio>
#include<cstring>
#define popcnt __builtin_popcount
using namespace std;
const int N=17,M=1<<N,mod=1e9+7,inv=mod+1>>1;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m,tot;
int f[M],A[M];
int a[N+1][M],b[N+1][M],c[M],d[M],e[M];
inline int adj(int x){return (x>=mod)?x-mod:x;}
inline void FMT(int op,int n,int *a)
{
int tot=1<<n;
if(!op)
{
for(int i=0;i<n;i++)
for(int j=0;j<tot;j++)
if(j>>i&1)
a[j]=adj(a[j]+a[j^(1<<i)]);
}
else
for(int i=0;i<n;i++)
for(int j=0;j<tot;j++)
if(j>>i&1)
a[j^(1<<i)]=adj(a[j]+a[j^(1<<i)]);
}
inline void IFMT(int op,int n,int *a)
{
int tot=1<<n;
if(!op)
{
for(int i=0;i<n;i++)
for(int j=tot-1;~j;j--)
if(j>>i&1)
a[j]=adj(a[j]-a[j^(1<<i)]+mod);
}
else
for(int i=0;i<n;i++)
for(int j=tot-1;~j;j--)
if(j>>i&1)
a[j^(1<<i)]=adj(a[j^(1<<i)]-a[j]+mod);
}
inline void FWT(int n,int *a)
{
int tot=1<<n;
for(int mid=1;mid<tot;mid<<=1)
for(int i=0;i<tot;i+=mid<<1)
for(int j=0;j<mid;j++)
{
int x=a[i+j],y=a[i+j+mid];
a[i+j]=adj(x+y),a[i+j+mid]=adj(x-y+mod);
}
}
inline void IFWT(int n,int *a)
{
int tot=1<<n;
for(int mid=1;mid<tot;mid<<=1)
for(int i=0;i<tot;i+=mid<<1)
for(int j=0;j<mid;j++)
{
int x=a[i+j],y=a[i+j+mid];
a[i+j]=1ll*adj(x+y)*inv%mod,a[i+j+mid]=1ll*adj(x-y+mod)*inv%mod;
}
}
int main()
{
read(m);
for(int i=0;i<m;i++)
{
int x;
read(x);
A[x]++,tot=max(tot,x);
}
tot++;
while((1<<n)<tot)n++;
tot=1<<n;
f[0]=0,f[1]=1;
for(int i=2;i<tot;i++)
f[i]=adj(f[i-1]+f[i-2]);
for(int i=0;i<tot;i++)
a[popcnt(i)][i]=A[i];
for(int i=0;i<=n;i++)FMT(0,n,a[i]);
for(int i=0;i<=n;i++)
for(int j=0;j<=n-i;j++)
for(int x=0;x<tot;x++)
b[i+j][x]=adj(b[i+j][x]+1ll*a[i][x]*a[j][x]%mod);
for(int i=0;i<=n;i++)
IFMT(0,n,b[i]);
memcpy(c,A,sizeof(c));
FWT(n,c);
for(int i=0;i<tot;i++)
c[i]=1ll*c[i]*c[i]%mod;
IFWT(n,c);
for(int i=0;i<tot;i++)
d[i]=1ll*b[popcnt(i)][i]*f[i]%mod;
memcpy(e,A,sizeof(e));
for(int i=0;i<tot;i++)
c[i]=1ll*c[i]*f[i]%mod,e[i]=1ll*e[i]*f[i]%mod;
FMT(1,n,c),FMT(1,n,d),FMT(1,n,e);
for(int i=0;i<tot;i++)
c[i]=1ll*c[i]*d[i]%mod*e[i]%mod;
IFMT(1,n,c);
int ans=0;
for(int i=0;i<n;i++)
ans=adj(ans+c[1<<i]);
printf("%d\n",ans);
return 0;
}
|