fwt主要是用来处理一类卷积问题的
首先说明一下集合幂级数
这就是一个用集合作为下标的函数
而fwt可以处理一类与集合幂级数相关的卷积问题
我们考虑是一个关于集合的运算
现在有集合
我们需要求
其中是任意运算
如何处理这个问题
我们如果能构造出一种对于的变换，使得
(指对应位置运算，而不是卷积)
那么就可以对和变换，在算出后变换回来，得到答案
那么问题在于如何得到这种变换
我们考虑最高位的情况
我们定义为最高位为的变换结果，为最高位为的变换结果
现在如果可以用和表示，那问题就能解决
接下来我们对不同的运算具体分析
这里我们先定义()指直接将相接,后面会用到
xor
对于xor运算，我们可以发现
这里有个结论
推我不会，但证明应该谁都会
同理逆变换
代码
1
2
3
4
5
6
7
8
9
10
11
12
| void txor(lg *a,int n,int on=1){
int U=1<<n;
for(int i=2,p=1;i<=U;i<<=1,p<<=1){
for(int j=0;j<U;j+=i){
for(int k=j;k<j+p;++k){
lg A=a[k],B=a[k+p];
a[k]=(A+B)*on%Md;a[k+p]=(A-B)*on%Md;
if(a[k+p]<0)a[k+p]+=Md;
}
}
}
}
|
and
还是背结论吧
代码
1
2
3
4
5
6
7
8
9
10
11
| void tand(lg *a,int n,int on=1){
int U=1<<n;
for(int i=2,p=1;i<=U;i<<=1,p<<=1){
for(int j=0;j<U;j+=i){
for(int k=j;k<j+p;++k){
a[k]=(a[k]+a[k+p]*on)%Md;
if(a[k]<0)a[k]+=Md;
}
}
}
}
|
or
代码
1
2
3
4
5
6
7
8
9
10
11
| void tor(lg *a,int n,int on=1){
int U=1<<n;
for(int i=2,p=1;i<=U;i<<=1,p<<=1){
for(int j=0;j<U;j+=i){
for(int k=j;k<j+p;++k){
a[k+p]=(a[k+p]+a[k]*on)%Md;
if(a[k+p]<0)a[k+p]+=Md;
}
}
}
}
|
完整代码
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
| namespace Ura{
void txor(lg *a,int n,int on=1){
int U=1<<n;
for(int i=2,p=1;i<=U;i<<=1,p<<=1){
for(int j=0;j<U;j+=i){
for(int k=j;k<j+p;++k){
lg A=a[k],B=a[k+p];
a[k]=(A+B)*on%Md;a[k+p]=(A-B)*on%Md;
if(a[k+p]<0)a[k+p]+=Md;
}
}
}
}
void tand(lg *a,int n,int on=1){
int U=1<<n;
for(int i=2,p=1;i<=U;i<<=1,p<<=1){
for(int j=0;j<U;j+=i){
for(int k=j;k<j+p;++k){
a[k]=(a[k]+a[k+p]*on)%Md;
if(a[k]<0)a[k]+=Md;
}
}
}
}
void tor(lg *a,int n,int on=1){
int U=1<<n;
for(int i=2,p=1;i<=U;i<<=1,p<<=1){
for(int j=0;j<U;j+=i){
for(int k=j;k<j+p;++k){
a[k+p]=(a[k+p]+a[k]*on)%Md;
if(a[k+p]<0)a[k+p]+=Md;
}
}
}
}
}
|
