FWT

写在前面:
FWT 变换本质是对二进制进行拆分然后分治的策略,建议与sos dp一起学习,这样对比着来看,其实本质相同。
参考博客: FWT


FWT学习

<stron>
F W T ( A ) [ i ] = <munder> i j = j </munder> A [ j ] FWT(A)[i] = \sum_{i|j=j} A[j] FWT(A)[i]=ij=jA[j]
<stron>
F W T ( A ) [ i ] = <munder> i &amp; j = i </munder> A [ j ] FWT(A)[i] = \sum_{i\&amp;j = i} A[j] FWT(A)[i]=i&j=iA[j]
<stron>
F W T ( A ) [ i ] = <munder> d ( i &amp; j ) m o d 2 = 0 </munder> <munder> d ( i &amp; j ) m o d 2 = 1 </munder> A [ j ] FWT(A)[i] = \sum_{d(i\&amp;j) mod 2 = 0} - \sum_{d(i \&amp; j) mod 2 =1} A[j] FWT(A)[i]=d(i&j)mod2=0d(i&j)mod2=1A[j]</stron></stron></stron>

注: d ( i ) d(i) d(i)代表求 i i i二进制表示中 1 1 1的个数

FWT 用于集合卷积运算,类似FFT,但比FFT简单
C k = <munderover> i j = k </munderover> a i b i {C}_{k}=\sum_{i \oplus j=k}^{}a_i*b_i Ck=ij=kaibi
暴力求解 O ( n 2 ) O(n^2) O(n2), FWT就登场了,复杂度 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))网上讲FWT原理的满天飞,我就不再赘述了,主要看试题,如果一时半会儿看不懂原理,不妨先做看个模板题

bzoj4589: Hard Nim

Description
Claris和NanoApe在玩石子游戏,他们有n堆石子,规则如下:

  1. Claris和NanoApe两个人轮流拿石子,Claris先拿。
  2. 每次只能从一堆中取若干个,可将一堆全取走,但不可不取,拿到最后1颗石子的人获胜。
    不同的初始局面,决定了最终的获胜者,有些局面下先拿的Claris会赢,其余的局面Claris会负。
    Claris很好奇,如果这n堆石子满足每堆石子的初始数量是不超过m的质数,而且他们都会按照最优策略玩游戏,那么NanoApe能获胜的局面有多少种。
    由于答案可能很大,你只需要给出答案对10^9+7取模的值。

Input
输入文件包含多组数据,以EOF为结尾。
对于每组数据:
共一行两个正整数n和m。
每组数据有1<=n<=10^9, 2<=m<=50000。
不超过80组数据。

不会NIM博弈的先看一下
题目的意思翻译一下就是找不超过m的n个质数(可重复),异或和为零 的方案数有多少种
再看一下FWT解决的问题
C k = <munderover> i j = k </munderover> a i b i {C}_{k}=\sum_{i \oplus j=k}^{}a_i*b_i Ck=ij=kaibi
C k C_k Ck 表示 选取两个异或和为k的方案数有多少种, a i a_i ai 表示是否是质数,则有
C k = <munderover> i j = k </munderover> a i a i {C}_{k}=\sum_{i \oplus j=k}^{}a_i*a_i Ck=ij=kaiai
选取三个就是
C k = <munderover> i j = k </munderover> C i a i {C}_{k}=\sum_{i \oplus j=k}^{}C_i*a_i Ck=ij=kCiai
进行n次时 C 0 C_0 C0 就是所求的解
所以代码就是这样子

const int    mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
const int maxn = 1e5+100;
int  a[maxn];
int  b[maxn];
void init(){
    for(int i = 2;i < maxn; ++i) a[i] = 1;
    for(int i = 2;i < maxn; ++i ){
        if(a[i]){
          for(int j = i+i; j < maxn; j += i) a[j] = 0;
        }
    }
}
void FWT(int *a,int N,int opt){
    const int inv2 = qpow(2,mod-2);
    // j是区间开始点,i是区间距离,k是具***置,j+k,i+j+k就是在a数组中的坐标
    for(int i = 1;i < N; i <<= 1){
        for(int p = i<<1,j = 0;j < N; j += p){
            for(int k = 0;k < i; ++k){
                int X = a[j+k],Y = a[i+j+k];
                a[j+k] = (X+Y)%mod;
                a[i+j+k] = (X+mod-Y)%mod;
                if(opt == -1) a[j+k] = 1ll*a[j+k]*inv2%mod,
                a[i+j+k] = 1ll*a[i+j+k]*inv2%mod;
            }
        }
    }
}

int main(void)
{
          
    init();
    int n,m;
    while(cin>>n>>m){
        me(b);
        for(int i = 0;i <= m; ++i) b[i] = a[i];
        LL t = 2;
        while( t <= m) t <<= 1;
 
        FWT(b,t,1);
        for(int i = 0;i < t; ++i) b[i] = qpow(b[i],n);
        FWT(b,t,-1);
        printf("%d\n",b[0]);
    }
    return 0;
}


模板

// 异或
void FWT(int *a,int N,int opt){
	const int inv2 = qpow(2,mod-2);
	// j是区间开始点,i是区间距离,k是具***置,j+k,i+j+k就是在a数组中的坐标
	for(int i = 1;i < N; i <<= 1){
		for(int p = i<<1,j = 0;j < N; j += p){
			for(int k = 0;k < i; ++k){
                int X = a[j+k],Y = a[i+j+k];
                a[j+k] = (X+Y)%mod;
                a[i+j+k] = (X+mod-Y)%mod;
                if(opt == -1) a[j+k] = 1ll*a[j+k]*inv2%mod,a[i+j+k] = 1ll*a[i+j+k]*inv2%mod;


			}
		}
	}
}if(opt == 1) F[i+j+k] = (F[i+j+k]+F[j+k]) %mod;
else         F[i+j+k] = (F[i+j+k+mod-F[j+k]) %mod;if(opt == 1) F[j+k] = (F[j+k]+F[i+j+k]) %mod;
else F[j+k] = (F[j+k] +mod-F[i+j+k])%mod;

FWT 例题

1 bzoj4589: Hard Nim

FWT 模板题     
参考代码

2 H

根据线性基的概念推出最多去掉log(sumxor) 个,进行一次FWT然后相乘,求IFWT判断sumxor 是否可以推出     
参考代码

3. Tree Cutting HDU - 5909

树dp+FWT加速,先无根树转化成有根树,然后dfs树dp,对于每一个根而言,下面的子树选或者不选两个状态,然后用FWT加速集合卷积       、
参考代码

4. 622C Binary Table.cpp

状态压缩 、FWT
参考代码

5. Maxor

求一组数中,两两异或的最大值,并输出方案数,做一遍FWT,然后去重 a n s = ( a [ i ] n u m i n u m i n u m i ( n u m i 1 ) ) / 2 = ( a [ i ] n u m i ) / 2 ans = (a[i]-num_i*num_i-num_i*(num_i-1))/2=(a[i]-num_i)/2 ans=(a[i]numinuminumi(numi1))/2=(a[i]numi)/2
参考代码

博客历程

2018/08/21
刚刚会使用模板,然后写下了博文,诸多不足
Upd
2019/8/29:
增加了对FWT变换之后的解释公式
在这一年接触了不少关于 F W T FWT FWT的题目,可以说是FWT理解的更深了,不再局限于套模板的地步,也理解了FWT变换的原理,其实FWT和FFT本质不同,FWT是二进制的艺术,FFT是信号变换的理论,FFT只是借用了一些二进制的东西,FWT相比FFT要简单的多