概述

我们知道通过FFT可以在$O(nlogn)$的时间求多项式乘法
经常应用到求乘法的卷积上$( (f \otimes g)(n) = \sum_{i=0}^n f(i)g(n-i) )$
我们注意到每次算 $f(i)*g(j),i+j = n$

而当$i?j = n$时,我们就要用快速沃尔什变换(FWT)来求
其中?可以定义为任意一种位运算(包括复合位运算)

原理

由于位运算每一位是独立的
我们假设$A = (A_0,A_1)$,$B = (B_0,B_1)$,表示当前位为0和当前位为1
我们的目标就是求$C = A?B = (\sum_{j?k=0} A_j*B_k, \sum_{j?k=1} A_j*B_k)$
然后从高位到低位递归下去

假设构造一个变换$tf(A) * tf(B) = tf(C)$
我们要在短时间内求出$tf$及其逆变换$utf$,具体参考下述公式

公式

xor

$tf(A) = (tf(A_0) + tf(A_1),tf(A_0) - tf(A_1))$
$utf(A) = (utf(\frac{A_0+A_1}{2}),utf(\frac{A_0-A_1}{2}))$

and

$tf(A) = (tf(A_0) + tf(A_1),tf(A_1))$
$utf(A) = (utf(A_0) - tf(A_1),utf(A_1))$

or

$tf(A) = (tf(A_0),tf(A_1)+tf(A_0))$
$utf(A) = (utf(A_0),utf(A_1)-utf(A_0))$

nxor nand nor

当运算为异或非,与非和或非时
可以先用xor and or的方法求出来,然后交换每个互反的两位

模板

xor

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
void FWT(LL a[],int l,int r)
{
if(l == r) return;
int m = (l+r) >> 1;
FWT(a,l,m); FWT(a,m+1,r);
for(int i=0;i<=m-l;++i)
{
LL a0 = a[l+i],a1 = a[m+i+1];
a[l+i] = a0 + a1;
a[m+i+1] = a0 - a1;
}
}

void IFWT(LL a[],int l,int r)
{
if(l == r) return;
int m = (l+r) >> 1;
for(int i=0;i<=m-l;++i)
{
LL a0 = a[l+i],a1 = a[m+i+1];
a[l+i] = (a0 + a1)/2;
a[m+i+1] = (a0 - a1)/2;
}
IFWT(a,l,m); IFWT(a,m+1,r);
}

and

1
2
3
4
5
6
7
8
void FWT(LL a[],int l,int r,int v)	//v = 1变换 -1逆变换
{
if(l == r) return;
int m = (l+r) >> 1;
FWT(a,l,m,v); FWT(a,m+1,r,v);
for(int i=0;i<= m-l;++i)
a[l+i] += a[m+i+1]*v;
}

or

1
2
3
4
5
6
7
8
void FWT(LL a[],int l,int r,int v)	//v = 1变换 -1逆变换
{
if(l == r) return;
int m = (l+r) >> 1;
FWT(a,l,m,v); FWT(a,m+1,r,v);
for(int i=0;i<=m - l;++i)
a[m+i+1] += a[l+i]*v;
}

题目

TC SRM518 1000

有K(1e9)堆石子,每堆数量不超过L(5e4),问Nim游戏中先手必败的局面数量(这题石子数目为质数)

$f(i,k)$ 表示前i堆中异或和等于k的方案数
$f(i,k) = \sum_{x \, xor \, y = k}f(i-1,x)*f(1,y)$

然后用 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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int mod = 1e9 + 7,inv2 = 5e8 + 4;
const int maxn = 1 << 16;
LL a[maxn];

LL pow_m(LL a,int n)
{
LL res = 1;
while(n)
{
if(n&1) res = res*a%mod;
a = a*a%mod;
n >>= 1;
}
return res;
}

void FWT(LL a[],int l,int r)
{
if(l == r) return;
int m = (l+r) >> 1;
FWT(a,l,m); FWT(a,m+1,r);
for(int i=0;i<=m-l;++i)
{
LL a0 = a[l+i],a1 = a[m+i+1];
a[l+i] = (a0 + a1) %mod;
a[m+i+1] = (a0 - a1 + mod)%mod;
}
}

void IFWT(LL a[],int l,int r)
{
if(l == r) return;
int m = (l+r) >> 1;
for(int i=0;i<=m-l;++i)
{
LL a0 = a[l+i],a1 = a[m+i+1];
a[l+i] = (a0 + a1)%mod * inv2 %mod;
a[m+i+1] = ((a0 - a1 + mod)%mod*inv2) %mod;
}
IFWT(a,l,m); IFWT(a,m+1,r);
}

class Nim {
public:
int count(int K,int L) {
int len = 1;
while(len <= L) len <<= 1;
memset(a,0,sizeof a);
for(int i=2;i<=L;++i)
a[i] = 1;
for(int i=2;i<=L;++i)
if(a[i])
for(int j=i+i;j <= L;j+=i) a[j] = 0;
FWT(a,0,len-1);
for(int i=0;i<len;++i) a[i] = pow_m(a[i],K);
IFWT(a,0,len-1);
return int(a[0]);
}
};

/*
int main()
{
//freopen("test.txt","r",stdin);
Nim n;
int K,L;
while(cin >> K >> L)
cout << n.count(K,L) << '\n';
return 0;
}
*/

CF347-F

参考