后面的图片将会告诉:

如何推出FWT的公式tf

如何推出FWT的逆公式utf

用的是设系数,求系数的方法!

=========================================================

以一种高度思考

http://picks.logdown.com/posts/179290-fast-walsh-hadamard-transform

加和乘的定义

大小为1时的公式

https://blog.csdn.net/zhshrs/article/details/54838466

证明

https://blog.csdn.net/john123741/article/details/76576925

写成

or

tf(A)=(tf(A0),tf(A1)+tf(A0))

utf(A)=(utf(A0),utf(A1)-utf(A0))

and

tf(A)=(tf(A0)+tf(A1),tf(A1))

utf(A)=(utf(A0)-utf(A1),utf(A1))

xor

tf(A)=(tf(A0)+tf(A1),tf(A0)-tf(A1))

utf(A)=(1/2*(utf(A0)+utf(A1)),1/2*(utf(A0)-utf(A1)))

更好记忆一点

对于or,and

0 = 0 or 0 对应 or tf(A0)[utf(A0)]

1 = 1 and 1 对应 and tf(A1)[utf(A1)]

=================================

and or xor 二进制操作

0~2^(k-1)-1时,最高位为0

2^(k-1)~2^k-1时,最高位为1

e.g.

000

001

010

011

----

100

101

110

111

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

P.S.:

FFT和FWT,两者虽然实现方法都是内容分半(二分),但是其本质原理不同。

FFT: http://www.cnblogs.com/zwfymqz/p/8244902.html

快速莫比乌斯变换

study from :

https://yhx-12243.github.io/OI-transit/records/vijos%20%234.html

适用于and or,xor 行不通

FMT写法和FWT是一样的,两者考虑问题角度不一样。

https://www.luogu.org/problemnew/show/P4717

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

存储函数地址

void (*addr1[3])(ll a[])={fwt1,fwt2,fwt3};
    void (*addr2[3])(ll a[])={ufwt1,ufwt2,ufwt3};

also can use (int type)=1ll*...

注意当数字范围为[0,x]

遍历范围 [0,z) tot=2*x(大于any i op j, 其中i,j in [0,x])

而数组开z大小

对于代码中的tot,要写成2^k的形式,

否则如写成tot,e.g. tot=9,  8(i)+3(j)>9。

对应好记忆

 #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long const double eps=1e-;
const ll inf=1e9;
const ll mod=;
const int maxn=(<<)*; ///any n or <2n /**
补全为2^k
**/ ll aa[maxn],bb[maxn],a[maxn],b[maxn];
int tot;
ll mod_inv_2=(mod+)/; ///or
void fwt1(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j+cnt_pre]+=a[i+j])%=mod;
} void ufwt1(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j+cnt_pre]-=a[i+j]-mod)%=mod;
} ///and
void fwt2(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j]+=a[i+j+cnt_pre])%=mod;
} void ufwt2(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j]-=a[i+j+cnt_pre]-mod)%=mod;
} ///xor
void fwt3(ll *a)
{
int cnt_pre,cnt_cur,i,j;
ll x;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
{
x=a[i+j];
a[i+j]=(a[i+j]+a[i+j+cnt_pre])%mod;
a[i+j+cnt_pre]=(x-a[i+j+cnt_pre]+mod)%mod;
}
} void ufwt3(ll *a)
{
int cnt_pre,cnt_cur,i,j;
ll x;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
{
x=a[i+j];
a[i+j]=(a[i+j]+a[i+j+cnt_pre])*mod_inv_2%mod;
a[i+j+cnt_pre]=(x-a[i+j+cnt_pre]+mod)*mod_inv_2%mod; ///x-
}
} int main()
{
int n,i,j;
scanf("%d",&n);
tot=<<n;
for (i=;i<tot;i++)
scanf("%lld",&aa[i]);
for (i=;i<tot;i++)
scanf("%lld",&bb[i]); void (*addr1[]) (ll a[])={fwt1,fwt2,fwt3};
void (*addr2[]) (ll a[])={ufwt1,ufwt2,ufwt3}; for (i=;i<;i++)
{
memcpy(a,aa,sizeof(aa));
memcpy(b,bb,sizeof(bb));
(*addr1[i])(a);
(*addr1[i])(b);
for (j=;j<tot;j++)
a[j]=a[j]*b[j]%mod;
(*addr2[i])(a);
for (j=;j<tot;j++)
printf("%lld%c",a[j],j==tot-?'\n':' ');
}
return ;
}
/*
0
1000000
1000000 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
*/

对应下方的图片公式推导

tf  a0+a1  a1-a0

utf  a1    a0

 #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long const double eps=1e-;
const ll inf=1e9;
const ll mod=;
const int maxn=(<<)*; ///any n or <2n /**
补全为2^k
**/ ll aa[maxn],bb[maxn],a[maxn],b[maxn];
int tot;
ll mod_inv_2=(mod+)/; ///or
void fwt1(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j+cnt_pre]+=a[i+j])%=mod;
} void ufwt1(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j+cnt_pre]-=a[i+j]-mod)%=mod;
} ///and
void fwt2(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j]+=a[i+j+cnt_pre])%=mod;
} void ufwt2(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j]-=a[i+j+cnt_pre]-mod)%=mod;
} ///xor
void fwt3(ll *a)
{
int cnt_pre,cnt_cur,i,j;
ll x;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
{
x=a[i+j];
(a[i+j]+=a[i+j+cnt_pre])%=mod;
(a[i+j+cnt_pre]-=x-mod)%=mod; ///-x
}
} void ufwt3(ll *a)
{
int cnt_pre,cnt_cur,i,j;
ll x;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
{
x=a[i+j];
a[i+j]=(a[i+j]+a[i+j+cnt_pre])*mod_inv_2%mod;
a[i+j+cnt_pre]=(x-a[i+j+cnt_pre]+mod)*mod_inv_2%mod; ///x-
}
} int main()
{
int n,i,j;
scanf("%d",&n);
tot=<<n;
for (i=;i<tot;i++)
scanf("%lld",&aa[i]);
for (i=;i<tot;i++)
scanf("%lld",&bb[i]); void (*addr1[]) (ll a[])={fwt1,fwt2,fwt3};
void (*addr2[]) (ll a[])={ufwt1,ufwt2,ufwt3}; for (i=;i<;i++)
{
memcpy(a,aa,sizeof(aa));
memcpy(b,bb,sizeof(bb));
(*addr1[i])(a);
(*addr1[i])(b);
for (j=;j<tot;j++)
a[j]=a[j]*b[j]%mod;
(*addr2[i])(a);
for (j=;j<tot;j++)
printf("%lld%c",a[j],j==tot-?'\n':' ');
}
return ;
}
/*
0
1000000
1000000 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
*/

and,or,xor等操作

C=A@B @为卷积运算(通过两个函数生成第三个函数的一种数学算子)

目标:tf(C)=tf(A)*tf(B)

设置tf(X)=(... , ...) 使满足上述条件

基础部分

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

公式推导

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

验证公式正确性

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

快速沃尔什变换(FWT) 与 快速莫比乌斯变换 与 快速沃尔什变换公式推导-LMLPHP

05-17 14:27
查看更多