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