FWT小结

Contents
  1. 1. Ⅰ. 快速沃尔什变换认知
  2. 2. Ⅱ. 快速沃尔什变换
    1. 2.1. 形式
    2. 2.2. 计算
      1. 2.2.1. 变换
      2. 2.2.2. 分治
      3. 2.2.3. 三种位运算变换总结
    3. 2.3. 时间复杂度与写法
    4. 2.4. 位运算卷积与子集卷积
  3. 3. Ⅲ. 题目选讲
    1. 3.1. IForg 1028 Bob and Alice are playing numbers
    2. 3.2. SRM 518 NIM
    3. 3.3. Codeforces 449D Jzzhu and Numbers
  4. 4. Reference

Ⅰ. 快速沃尔什变换认知

  • 这东西英文名叫$Fast Walsh$-$Hadamard Transform$
  • $FWT$是用来快速计算位运算卷积的,至于什么是卷积,可以先学习一下$FFT$
  • FFT小结,点击链接
  • 既然提到了位运算,必然要和子集扯上关系,也就是说可以来求子集卷积

Ⅱ. 快速沃尔什变换

形式

  • 类似于$FFT$的卷积形式,假设$\otimes$为卷积符号,对于$2$个等长的系数向量$\overrightarrow{a}$和$\overrightarrow{b}$
  • 对于它们的卷积$\overrightarrow{c}=\overrightarrow{a}⊗\overrightarrow{b}$,有$C_k= \displaystyle \sum_{i\otimes j=k} A_i \times B_j$
  • 其实当$\otimes$为$+$的时候,就是普通的卷积形式了

计算

假设$2$个向量长度都是$n$,那么暴力计算位运算卷积是$O(n^2)$的

变换

  • 类比$FFT$,假设我们知道一种类似于$DFT$的变换$tf$,可以使向量$X$产生一个新向量$tf(X)$
  • 以及类似于$IDFT$的变换$utf$,能使得$utf(tf(X))=X$
  • 并且变换$tf$必须具有这样的性质:$tf(X\otimes Y)=tf(X)\times tf(Y)$

分治

  • 类比$FFT$,我们考虑分治,接下来为了方便,我们令$\otimes$为$xor$运算,即$\oplus$
  • 令$Z=X\otimes Y$
  • 考虑$X$和$Y$都只有$1$个元素的时候,此时不需要变换,显然有$Z_{0\oplus 0=0}=X_0 \times Y_0$,即满足$tf(X)=X=utf(X)$
  • 考虑各有$2$个元素的时候,令$X=(a, b), Y=(c, d)$,此时$Z$
    $Z_0=ac+bd, Z_1=ad+bc$,即$(a, b)\otimes (c, d)=(ac + bd, ad + bc)$

  • 令$tf(a, b) = (a - b, a + b)$
    那么$tf(a, b) \times tf(c, d)$
    $= (a - b, a + b) \times (c - d, c + d)$
    $= ( (a-b)\times(c-d) , (a+b)\times(c+d) )$
    $= ( ac - ad - bc + bd, ac + ad + bc + bd )$
    $ = ( ac + bd - ad - bc, ac + bd + ad + bc )$
    $= tf( ac + bd, ad + bc )$
    $ = tf( (a,b) \otimes (c,d ) )$
  • 显然我们可以发现,对于偶数长度的向量,均分成$2$个向量都满足这个性质
  • 当然也可以用数学归纳法证一波,具体去看Reference里的证明吧
  • 之后我们就可以利用这个性质来递归的变换
  • 令$X$是个偶数长度的向量,且$X=(X1, X2)$,$X1$和$X2$各是$X$的一半
  • 那么有$tf(X1, X2) = (tf(X1) - tf(X2), tf(X1) + tf(X2))$
  • 具体就是先递归变换$2$个等长的子序列,$X1$和$X2$都递归变换过了,
    那么新的$X1=X1-X2$,同理新的$X2=X1+X2$

  • 当然逆变换$utf$也很好构造,只需要反向回去就好了,每次解一下方程
  • 令$Y1 = tf(X1) - tf(X2), Y2 = tf(X1) + tf(X2)$,
    现在$Y1$和$Y2$已知,解出$tf(X1)$和$tf(X2)$即可

三种位运算变换总结

  • $tfxor(A)=(tfxor(A_0+A_1), tfxor(A_0−A_1))$
    $utfxor(A)=(utfxor( (A_0+A_1)/2), utfxor( (A_0−A_1)/2))$
  • $tfand(A)=(tfand(A_0+A_1), tfand(A_1))$
    $utfand(A)=(utfand(A_0−A_1), utfand(A_1))$
  • $tfor(A)=(tfor(A_0), tfor(A_1+A_0))$
    $utfor(A)=(utfor(A_0), utfor(A_1−A_0))$

时间复杂度与写法

  • 时间复杂度$T(n) = 2T(n/2)+O(n)$,根据主定理为$O(nlogn)$
  • 写法就跟$FFT$类似了,先把长度扩展到$2$的幂次,之后按照前面说的分治就好了
  • 具体可以参照下面的板子题

位运算卷积与子集卷积

  • 我没有太深的理解,基本的理解就是,其实它们是共通的
  • 把数看成二进制下的子集,那么 & 便是集合交,| 是集合并,^ 是集合对称差
  • 所以很多时候题目可以从这$2$个角度都能说通,也提供了另一个思维方向

Ⅲ. 题目选讲

IForg 1028 Bob and Alice are playing numbers

分析:
板子题,$n$个数里选$2$个数进行三种位运算的最大值
数的大小只有$10^6$,$cnt[i]:=i$这个数出现了多少次
然后卷积一下自己,减去自己和自己的,倒着枚举找到最大的那个就做完了

代码:

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
//
// Created by TaoSama on 2016-09-09
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
typedef long long LL;
LL quick(LL x, LL n) {
LL ret = 1;
for(; n; n >>= 1) {
if(n & 1) ret = ret * x % MOD;
x = x * x % MOD;
}
return ret;
}
const LL invTwo = quick(2, MOD - 2);
void fwtXor(LL* a, int len) {
if(len == 1) return;
int h = len >> 1;
fwtXor(a, h);
fwtXor(a + h, h);
for(int i = 0; i < h; ++i) {
LL x1 = a[i];
LL x2 = a[i + h];
a[i] = (x1 + x2) % MOD;
a[i + h] = (x1 - x2 + MOD) % MOD;
}
}
void ifwtXor(LL* a, int len) {
if(len == 1) return;
int h = len >> 1;
for(int i = 0; i < h; ++i) {
// y1=x1+x2
// y2=x1-x2
LL y1 = a[i];
LL y2 = a[i + h];
a[i] = (y1 + y2) * invTwo % MOD;
a[i + h] = (y1 - y2 + MOD) * invTwo % MOD;
}
ifwtXor(a, h);
ifwtXor(a + h, h);
}
void fwtAnd(LL* a, int len) {
if(len == 1) return;
int h = len >> 1;
fwtAnd(a, h);
fwtAnd(a + h, h);
for(int i = 0; i < h; ++i) {
LL x1 = a[i];
LL x2 = a[i + h];
a[i] = (x1 + x2) % MOD;
a[i + h] = x2;
}
}
void ifwtAnd(LL* a, int len) {
if(len == 1) return;
int h = len >> 1;
for(int i = 0; i < h; ++i) {
// y1=x1+x2
// y2=x2
LL y1 = a[i];
LL y2 = a[i + h];
a[i] = (y1 - y2 + MOD) % MOD;
a[i + h] = y2;
}
ifwtAnd(a, h);
ifwtAnd(a + h, h);
}
void fwtOr(LL* a, int len) {
if(len == 1) return;
int h = len >> 1;
fwtOr(a, h);
fwtOr(a + h, h);
for(int i = 0; i < h; ++i) {
LL x1 = a[i];
LL x2 = a[i + h];
a[i] = x1;
a[i + h] = (x2 + x1) % MOD;
}
}
void ifwtOr(LL* a, int len) {
if(len == 1) return;
int h = len >> 1;
for(int i = 0; i < h; ++i) {
// y1=x1
// y2=x2+x1
LL y1 = a[i];
LL y2 = a[i + h];
a[i] = y1;
a[i + h] = (y2 - y1 + MOD) % MOD;
}
ifwtOr(a, h);
ifwtOr(a + h, h);
}
int n, op;
const int C = 1 << 20;
LL a[N], cnt[C + 10];
int gao() {
for(int i = C; ~i; --i) if(cnt[i]) return i;
return -1;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &op);
memset(cnt, 0, sizeof cnt);
for(int i = 1; i <= n; ++i) {
scanf("%lld", a + i);
++cnt[a[i]];
}
static int kase = 0;
printf("Case #%d: ", ++kase);
if(op == 1) {
fwtAnd(cnt, C);
for(int i = 0; i < C; ++i) cnt[i] = cnt[i] * cnt[i] % MOD;
ifwtAnd(cnt, C);
for(int i = 1; i <= n; ++i) --cnt[a[i] & a[i]];
printf("%d\n", gao());
} else if(op == 2) {
fwtXor(cnt, C);
for(int i = 0; i < C; ++i) cnt[i] = cnt[i] * cnt[i] % MOD;
ifwtXor(cnt, C);
for(int i = 1; i <= n; ++i) --cnt[a[i] ^ a[i]];
printf("%d\n", gao());
} else {
fwtOr(cnt, C);
for(int i = 0; i < C; ++i) cnt[i] = cnt[i] * cnt[i] % MOD;
ifwtOr(cnt, C);
for(int i = 1; i <= n; ++i) --cnt[a[i] | a[i]];
printf("%d\n", gao());
}
}
return 0;
}

SRM 518 NIM

题意:
$2$个人玩$nim$游戏,能选$K\le 10^9$堆,每堆必须是素数$p_i\le L\le 10^6$,后手赢的方案数

分析:
$nim$游戏,由$SG$定理知,先手$xorsum$为$0$输,即后手赢
问题就变成了这个,之后就可以$dp$了,$f[i][j]:=$选$i$堆异或和为$j$的方法数
显然$f[1][j]$是知道的,转移是$f[i][j]=\displaystyle\sum_{x\oplus y=j} f[i-1][x] \times f[1][y]$
发现这是个$and$卷积的形式,答案就是卷积的$k$次幂,所以直接做就好了

主要代码:

1
2
3
4
fwtXor(a, L)
a[i] = a[i] ^ k
ifwtXor(a, L)
ans = a[0]

Codeforces 449D Jzzhu and Numbers

题意:
给定长度为$N\le 10^6$的数列,$A_i\le 10^6$,选出$0<k\le N$个数
使得它们二进制与起来的值为$0$,求方法数
分析:
题解给了一个容斥的做法,是基于子集卷积的
$f[s]:=$子集状态为$s$的方法数,$g[s]:=s$中$1$的个数
$f[s]$可由$fwt$子集卷积变换得到,之后我们根据容斥原理:
$ans=2^n+\displaystyle\sum_{s=1}^{2^{20}-1}(-1)^{g(s)}\cdot2^{f(s)}$,这里空集被容斥掉了
事实上,可以不用自己容斥,无论是哪种理解,对于某个$f[s]$,可以随便选
即变成$2^{f[s]}$,然后再$ifwt$变换回去,答案就是$f[0]$,这里空集同样被容斥掉了
从这里我们看出其实卷积也有容斥的感觉
(试了一下代码发现$fwt$变换其实就是所谓的高维前缀和)

代码:

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
//
// Created by TaoSama on 2016-09-09
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
typedef long long LL;
void fwtAnd(LL* a, int len) {
if(len == 1) return;
int h = len >> 1;
fwtAnd(a, h);
fwtAnd(a + h, h);
for(int i = 0; i < h; ++i) {
LL x1 = a[i];
LL x2 = a[i + h];
a[i] = (x1 + x2) % MOD;
a[i + h] = x2 % MOD;
}
}
void ifwtAnd(LL* a, int len) {
if(len == 1) return;
int h = len >> 1;
for(int i = 0; i < h; ++i) {
// y1=x1+x2
// y2=x2
LL y1 = a[i];
LL y2 = a[i + h];
a[i] = (y1 - y2 + MOD) % MOD;
a[i + h] = y2 % MOD;
}
ifwtAnd(a, h);
ifwtAnd(a + h, h);
}
int n;
const int C = 1 << 20;
LL cnt[C + 10], two[C + 10];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
two[0] = 1;
for(int i = 1; i < C; ++i) two[i] = two[i - 1] * 2 % MOD;
while(scanf("%d", &n) == 1) {
memset(cnt, 0, sizeof cnt);
for(int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
++cnt[x];
}
fwtAnd(cnt, C);
for(int i = 0; i < C; ++i) cnt[i] = two[cnt[i]];
ifwtAnd(cnt, C);
printf("%I64d\n", cnt[0]);
}
return 0;
}

Reference


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到