pre：

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

(思路与后续不同，思考如何和后续统一)

 

以一种高度思考

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

完善

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

代码参考

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

 

P.S.:

FFT和FWT，两者虽然某些原理(两分，使用重复项来降低时间复杂度)相似，但是，两个算法风马牛不相及！

 

 

快速莫比乌斯变换

study from :

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

适用于and or，xor 行不通

 

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

 

存储函数地址

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

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

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

 

1 #include 
     
        2 using namespace std;  3   4 #define ll long long  5 const int maxn=1<<17;  6 const ll mod=998244353;  7 const ll inv2=(mod+1)/2;  8   9 ll a[maxn],b[maxn],x[maxn],y[maxn]; 10 int w,n; 11  12 ///or 13 void fwt1(ll a[]) 14 { 15     int i,j,k,l; 16     for (i=2,l=1;i<=n;i<<=1,l<<=1)        ///range 17         for (j=0;j