FWT总结

花了一段时间把FWT技能给点了，姑且在这里记录下我对FWT的理解，其中大部分内容参考这个博客

首先，要知道FWT是用来处理这类问题的：

Ck=∑i⊗j=kAi∗Bj

其中异或可以换成其他位运算（&，|）

也可以叫它位运算卷积

对于其详细介绍以及如何在 nlogn 下完成可以看看这个博客，大概的过程就是把利用FWT把 A,B 转换成 A′,B′ ，然后有关系式

C′k=A′k∗B′k

，然后再把 C′ 进行反变换ifwt变成 C

然后贴一份模板

typedef long long ll;
const int mod = +;

ll mypow(ll x, ll n) {
    ll ret = ;
    for (; n; n >>= ) {
        if (n & ) ret = ret * x % mod;
        x = x * x % mod;
    }
    return ret;
}

const ll inv2 = mypow(, mod - );

void fwtXor(ll* a, int len) {
    if (len == ) return;
    int h = len >> ;
    fwtXor(a, h);
    fwtXor(a + h, h);
    for (int i = ; i < h; ++i) {
        ll x1 = a[i];
        ll x2 = a[i + h];
        a[i] = (x1 + x2) % mod;
        a[i + h] = (x1 - x2 + mod) % mod;
    }
}

void ifwtXor(ll* a, int len) {
    if (len == ) return;
    int h = len >> ;
    for (int i = ; i < h; ++i) {
        // y1=x1+x2
        // y2=x1-x2
        ll y1 = a[i];
        ll y2 = a[i + h];
        a[i] = (y1 + y2) * inv2 % mod;
        a[i + h] = (y1 - y2 + mod) * inv2 % mod;
    }
    ifwtXor(a, h);
    ifwtXor(a + h, h);
}

void fwtAnd(ll* a, int len) {
    if (len == ) return;
    int h = len >> ;
    fwtAnd(a, h);
    fwtAnd(a + h, h);
    for (int i = ; i < h; ++i) {
        ll x1 = a[i];
        ll x2 = a[i + h];
        a[i] = (x1 + x2) % mod;
        a[i + h] = x2;
    }
}

void ifwtAnd(ll* a, int len) {
    if (len == ) return;
    int h = len >> ;
    for (int i = ; i < h; ++i) {
        // y1=x1+x2
        // y2=x2
        ll y1 = a[i];
        ll y2 = a[i + h];
        a[i] = (y1 - y2 + mod) % mod;
        a[i + h] = y2;
    }
    ifwtAnd(a, h);
    ifwtAnd(a + h, h);
}

void fwtOr(ll* a, int len) {
    if (len == ) return;
    int h = len >> ;
    fwtOr(a, h);
    fwtOr(a + h, h);
    for (int i = ; i < h; ++i) {
        ll x1 = a[i];
        ll x2 = a[i + h];
        a[i] = x1;
        a[i + h] = (x2 + x1) % mod;
    }
}

void ifwtOr(ll* a, int len) {
    if (len == ) return;
    int h = len >> ;
    for (int i = ; i < h; ++i) {
        // y1=x1
        // y2=x2+x1
        ll y1 = a[i];
        ll y2 = a[i + h];
        a[i] = y1;
        a[i + h] = (y2 - y1 + mod) % mod;
    }
    ifwtOr(a, h);
    ifwtOr(a + h, h);
}

//len为2的幂
int len =  << ;
void FWT(ll *a, ll *b, ll *c, int len) {
    fwtXor(a, len);
    fwtXor(b, len);
    for (int i = ; i < len; ++i) {
        c[i] = a[i] * b[i] % mod;
    }
    ifwtXor(c, len);
}

道理我都懂，但是如何做题呢？

总之先做两题再说吧

Bob and Alice are playing numbers

题意：给你一个数组A，和一个二元位运算符 op ，让你选择其中两个数 i 和j，使得 i op j 最大

题解：纯粹的模板题，用来验算模板正确性
- color II
  
  题意：求图的最小染色数，按题目要求输出答案
  
  题解：图的最小染色数是经典的NP问题，显然可以看到这样一个规律：同一种颜色的点一定构成一个独立集。对于一个集合 s ，有最小染色数F[s]，枚举它的一个独立子集 p ，便有dp方程
  
  F[s]=minp⊆sF[s−p]+1
  
  如果直接枚举子集，那么复杂度为 3n ，但是如果我们加一维，设 F[i][s] 表示用 i 种颜色染集合s的方案数，那么就能得到dp方程
  
  F[i][s]=∑x|y=sF[i−1][x]∗F[1][y]
  
  那么对于一个 s ，最小的不为零的i便是答案。虽然这里的 x 和y会重叠，但是最优解一定不会重叠所以萌大奶。利用FWT加速复杂度降至 n22n 。
  
  具体可以参考这个讨论和这个博客
- Binary Table
  
  题意：给你一个 20*100000 的01表，每次操作可以选择翻转某一行或者某一列，问你在这些操作下可以得到的最少的1的个数。
  
  题解：此题如果去看官方题解，大概会智商爆炸，而且复杂度再怎么优化也得 n22n 。但是用FWT就厉害了
  
  首先容易看到行只有20，所以我们可以二进制枚举行的翻转情况，用 x 来表示。然后对于每一列的值可以二进制表示为y，那么对于每一种 x ，这一列会变成z=x⊗y，然后根据 z 的1的个数来判断列是否要翻转。根据异或的性质，我们可以把表达式转换成x=z⊗y。
  
  我们设数组 Y[i] 表示 y=i 的个数， Z[i] 表示在二进制 i 下min(0的个数，1的个数)。然后对这两个数组FWT得
  
  X[i]=∑j⊗k=iY[j]∗Z[k]
  
  也就是对于每一列的初态和终态进行FWT，然后 X[i] 就能神奇的表示为行翻转为 i 下最小的1的个数啦，是不是很神奇，而且复杂度轻轻松松n2n
  
  具体代码可以参考这个博客
- 显然上面的题都是找到位运算卷积的表达式后用FWT加速，但是感觉还不够呐，需要更加深♂入理解FWT才行！
  
  首先来看CF上一道题
  - Jzzhu and Numbers
    
    题意：给你一个数组 A ，问你有多少个子集，使得这个子集每个数&运算后等于0
    
    题解：看起来跟FWT没有卵关系，事实上官方题解给的解法确实跟FWT没有任何卵关系。官方题解是这样的：不妨把每个数看成一个集合，先求出数组A里有多少个数是集合 s 的超集，设有dp[s]个。那么在这些数里面任意选，也就是有 2dp[s]−1 种方案&运算后至少为 s ，然后对着这个东西做一波容斥便能得到结果。
  上面解法的关键在于如何快速的求dp[s]，而且只能在 nlogn 的时间内完成。按一般思路是先把数组 A 放到相应的dp[s]里，然后这样做
```
for (int i = (<<)-; i >= ; --i) {
    for (int j = ; j < ; ++j) {
        if ((i>>j & ) == ) {
            dp[i] += dp[i | ( << j)];
        }
    }
}
           
```
  显然的，这样是有重的，但是如果把两个for循环调个位置
```
for (int i = ; i < ; ++i) {
    for (int j = ; j <  << ; ++j) {
        if ((j >> i & ) == ) {
            dp[j] += dp[j | ( << i)];
        }
    }
}
           
```
  就能神奇的去重啦，不信的话自己写两组小数据画一画大概就知道这是怎么去重的了。
  
  然后这东西有个名字，叫做高维前缀和。
  
  代码如下：
```
#include <stdio.h>
#include <algorithm>
#include <set>
#include <string.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <bitset>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int inf = ;
const double PI = acos(-);
const double eps = ;
const int maxn = ( << ) + ;
const int mod =  + ;

int n;
int dp[maxn];
int pow2[maxn];

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif

    pow2[] = ;
    for (int i = ; i < maxn; ++i) {
        pow2[i] = pow2[i - ] *  % mod;
    }

    scanf("%d", &n);
    for (int i = ; i < n; ++i) {
        int x;
        scanf("%d", &x);
        dp[x]++;
    }

    for (int i = ; i < ; ++i) {
        for (int j = ; j <  << ; ++j) {
            if ((j >> i & ) == ) {
                dp[j] += dp[j | ( << i)];
            }
        }
    }

    ll ans = ;
    for (int i = ; i <  << ; ++i) {
        int k = ;
        for (int j = ; j < ; ++j) {
            if (i >> j & ) k *= -;
        }

        ans += k * (pow2[dp[i]] - );
        ans %= mod;
    }

    printf("%I64d\n", (ans + mod) % mod);

}
           
```
  那么这题跟FWT又有什么卵关系呢，别急，首先你需要看这么一个东西炫酷反演魔术
  
  what？反演？莫比乌斯那个东西？你仿佛在逗我！
  
  回想一下莫比乌斯反演是干嘛的：我想要求 G[i] ，但是不好求，然后我找一个 F[n]=∑d|nG[d] ， F[i] 好求，最后通过 G[n]=∑d|nμ(nd)F[d] 来求得
  
  而FWT又如何呢：我想要求 C[k]=∑i⊗j=kA[i]∗B[j] ，但是不好求，然后我找一个 C′[k]=fwt(C[k]) ，而 C′[k]=A′[k]∗B′[k] ，好求，最后通过 C[k]=ifwt(C′[k]) 来得到
  
  这tm过程不是一样的吗！！！
  
  这一过程统称反演，然后你就需要安安心心看上面那个反演魔术了，其中里面的FWT要比开头那篇博客的一堆数学证明要好懂的多好懂个奶子
  
  根据上面的魔术的一个结论，在 or 卷积下，我们FWT要求的 C[i] 和 C′[i] 有这样一个关系：
  
  C′[i]=∑j⊆iC[j]
  
  嗯？这不就是高维前缀和吗！（子集就是 or 卷积，超集就是 and 卷积）
  
  教练，我不信啊！
  
  没关系，上面不是有个高维前缀和的AC代码么
  
  我们把这段代码
```
for (int i = ; i < ; ++i) {
    for (int j = ; j <  << ; ++j) {
        if ((j >> i & ) == ) {
            dp[j] += dp[j | ( << i)];
        }
    }
}
           
```
  换成这个
```
fwtAnd(dp,  << );
           
```
  提交上去，居然A了！(捂脸.jpg)
  
  不仅如此，我们看看魔术里面还有这么一条关系
  
  C[i]=∑j⊆i(−1)|i|−|j|C′[j]
  
  嗯。。。奇减偶加，略有所闻，江湖人称容斥。。。
  
  上面那题好像也要做容斥诶，试一下咯
  
  把这个
```
ll ans = ;
for (int i = ; i <  << ; ++i) {
    int k = ;
    for (int j = ; j < ; ++j) {
        if (i >> j & ) k *= -;
    }

    ans += k * (pow2[dp[i]] - );
    ans %= mod;
}
printf("%I64d\n", (ans + mod) % mod);
           
```
  改成这个
```
for (int i = ; i <  << ; ++i) {
    dp[i] = pow2[dp[i]];
}
ifwtAnd(dp,  << );
printf("%I64d\n", dp[]);
           
```
  嗯，也A了。。。
  
  贴个最终代码吧
```
#include <stdio.h>
#include <algorithm>
#include <set>
#include <string.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <bitset>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int inf = ;
const double PI = acos(-);
const double eps = ;
const int maxn = ( << ) + ;
const int mod =  + ;

void fwtAnd(ll* a, int len) {
    if (len == ) return;
    int h = len >> ;
    fwtAnd(a, h);
    fwtAnd(a + h, h);
    for (int i = ; i < h; ++i) {
        ll x1 = a[i];
        ll x2 = a[i + h];
        a[i] = (x1 + x2) % mod;
        a[i + h] = x2;
    }
}

void ifwtAnd(ll* a, int len) {
    if (len == ) return;
    int h = len >> ;
    for (int i = ; i < h; ++i) {
        // y1=x1+x2
        // y2=x2
        ll y1 = a[i];
        ll y2 = a[i + h];
        a[i] = (y1 - y2 + mod) % mod;
        a[i + h] = y2;
    }
    ifwtAnd(a, h);
    ifwtAnd(a + h, h);
}


int n;
ll dp[maxn];
int pow2[maxn];

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif

    pow2[] = ;
    for (int i = ; i < maxn; ++i) {
        pow2[i] = pow2[i - ] *  % mod;
    }

    scanf("%d", &n);
    for (int i = ; i < n; ++i) {
        int x;
        scanf("%d", &x);
        dp[x]++;
    }

    fwtAnd(dp,  << );

    for (int i = ; i <  << ; ++i) {
        dp[i] = pow2[dp[i]];
    }
    ifwtAnd(dp,  << );

    printf("%I64d\n", dp[]);

}
           
```
  到这里FWT差多就搞定了，嘛，还是有点因崔斯汀，虽然题目好像不多比较冷门就是了。。。

FWT总结

继续阅读

POJ_1985_Cow Marathon(树的直径)

CF1394C 计算几何

leetcode_17.Letter Combinations of a Phone Number

HDU 1286 找新朋友（欧拉函数模板）

hdu 1286 找新朋友（欧拉函数）

哈理工oj Touring （最短路 dij算法邻接表 + 队列）

HDU 1286 找新朋友(欧拉函数)找新朋友

HDU 5119 Happy Matt Friends（dp） Happy Matt Friends

CF-346 D. Robot Control(反向建图spfa)

ACMer成长之路

pat（B）1009. 说反话（逆迭代器）

关于多项式的一点研究及其在ACM竞赛中的应用关于多项式的一点研究及其在ACM竞赛中的应用

codeforces 838D D. Airplane Arrangements 构造法推公式

HDU Reorder the Books

POJ 1284 Primitive Roots (欧拉函数&原根定理)

hdu 4741 Save Labman No.004（计算几何） Save Labman No.004