第七节 快速沃尔什变换 (FWT)
|
166
|
0
|
第四章 多项式与数值积分

1188 字
|
21 分钟

Contents

快速沃尔什变换

例题：P4717 【模板】快速沃尔什变换 (FWT)

题目描述

给定长度为 2^n 两个序列 A,B，设

C_i=\sum_{j\oplus k = i}A_j \times B_k

分别当 \oplus 是 or,and,xor 时求出 C

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += P);
}

namespace FWT {
    int extend(int n) {
        int N = 1;
        for (; N < n; N <<= 1);
        return N;
    }
    void FWTor(vector<int> &a, bool rev) {
        int n = (int)a.size();
        for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
            for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
                if (!rev) add(a[i + j + m], a[i + j]);
                else sub(a[i + j + m], a[i + j]);
            }
        }
    }
    void FWTand(vector<int> &a, bool rev) {
        int n = (int)a.size();
        for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
            for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
                if (!rev) add(a[i + j], a[i + j + m]);
                else sub(a[i + j], a[i + j + m]);
            }
        }
    }
    void FWTxor(vector<int> &a, bool rev) {
        int n = (int)a.size(), inv2 = (P + 1) >> 1;
        for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
            for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
                int x = a[i + j], y = a[i + j + m];
                if (!rev) {
                    a[i + j] = (x + y) % P;
                    a[i + j + m] = (x - y + P) % P;
                } else {
                    a[i + j] = 1LL * (x + y) * inv2 % P;
                    a[i + j + m] = 1LL * (x - y + P) * inv2 % P;
                }
            }
        }
    }
    vector<int> Or(vector<int> a1, vector<int> a2) {
        int n = (int)max(a1.size(), a2.size()), N = extend(n);
        a1.resize(N); FWTor(a1, false);
        a2.resize(N); FWTor(a2, false);
        vector<int> A(N);
        for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
        FWTor(A, true);
        return A;
    }
    vector<int> And(vector<int> a1, vector<int> a2) {
        int n = (int)max(a1.size(), a2.size()), N = extend(n);
        a1.resize(N); FWTand(a1, false);
        a2.resize(N); FWTand(a2, false);
        vector<int> A(N);
        for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
        FWTand(A, true);
        return A;
    }
    vector<int> Xor(vector<int> a1, vector<int> a2) {
        int n = (int)max(a1.size(), a2.size()), N = extend(n);
        a1.resize(N); FWTxor(a1, false);
        a2.resize(N); FWTxor(a2, false);
        vector<int> A(N);
        for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
        FWTxor(A, true);
        return A;
    }
}
using namespace FWT;

int main() {
    int n;
    scanf("%d", &n); n = 1 << n;
    vector<int> a1(n), a2(n), A;
    for (int i = 0; i < n; i++) scanf("%d", &a1[i]);
    for (int i = 0; i < n; i++) scanf("%d", &a2[i]);
    A = Or(a1, a2);
    for (int i = 0; i < n; i++) {
        printf("%d%c", A[i], " \n"[i == n - 1]);
    }
    A = And(a1, a2);
    for (int i = 0; i < n; i++) {
        printf("%d%c", A[i], " \n"[i == n - 1]);
    }
    A = Xor(a1, a2);
    for (int i = 0; i < n; i++) {
        printf("%d%c", A[i], " \n"[i == n - 1]);
    }
    return 0;
}

FWT 转移 DP

题目：hdu5909 Tree Cutting

题目大意：

给一棵 n 个节点的树，每个节点都有一个小于 m 的权值；定义一棵子树的权值为所有节点的异或和，问权值为 0\cdots m-1 的所有子树的个数。

解题思路：

考虑树形 DP。设 f[i][j] 表示 以 i 为根的子树，且必须选择 i 这个节点，权值为 j 的子树个数（这里即子树的子树）。转移的时候，我们可以依次将根节点的子树和根结点合并，使用 FWT 来进行 xor 卷积转移。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
void add(int &x, int y) {}
void sub(int &x, int y) {}
namespace FWT {
    int extend(int n) {}
    void FWTxor(vector<int> &a, bool rev) {}
    vector<int> Xor(vector<int> a1, vector<int> a2) {}
}
using namespace FWT;

const int N = 1050;
int n, m;
int a[N], ans[N];
vector<int> f[N];
int head[N], tot;
struct Edge {
    int nex, to;
}eg[N << 1];
void addedge(int a, int b) {
    eg[++tot] = (Edge){head[a], b};
    head[a] = tot;
}

void dfs(int u, int fa) {
    f[u][a[u]] = 1;
    for (int i = head[u]; i; i = eg[i].nex) {
        int to = eg[i].to;
        if (to == fa) continue;
        dfs(to, u);
        vector<int> tmp = FWT::Xor(f[u], f[to]);
        for(int j = 0; j < m; j++) add(f[u][j], tmp[j]);
    }
    for (int i = 0; i < m; i++) add(ans[i], f[u][i]);
}

void init() {
    memset(head, 0, sizeof(head)); tot = 0;
    memset(ans, 0, sizeof(ans));
    for (int i = 1; i <= n; i++) {
        f[i].clear(); f[i].resize(m);
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        init();
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1, a, b; i < n; i++) {
            scanf("%d%d", &a, &b);
            addedge(a, b); addedge(b, a);
        }
        dfs(1, -1);
        for (int i = 0; i < m; i++) {
            printf("%d%c", ans[i], i == m - 1 ? '\n' : ' ');
        }
    }
    return 0;
}

求最大异或和

例题：2020 牛客多校第二场 E. Exclusive OR

题目大意

给定 n 个数，从中选择恰好 i 个数，要求其异或和最大。
对于 i\in[1\cdots n] 分别输出答案。

解题思路：

注意到 A[i]<2^{18}。由线性基的知识可知，这一组数的线性基大小为 18，因此最多选取 18 个数后可以得到最大异或和。因此当 i\ge 20 时，ans[i]=ans[i-2]：显然 ans[i]\ge ans[i-2]，若 ans[i]>ans[i-2]，说明至少选取 i-1 个数才到达最大值。因此我们只需求出前 19 个答案。
对 A 数组含有的数作为下标，进行异或卷积，得到的新数组如果某下标的值不为 0，则说明可以异或出这个数。我们进行 18 次异或卷积即可得到答案。

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
int extend(int n) {}
void FWTxor(vector<int> &a, bool rev) {}
vector<int> Xor(vector<int> a1, vector<int> a2) {}

int qmax(vector<int> &a) {
    for (int i = (1 << 18) - 1; i; i--) {
        if (a[i]) return i;
    }
    return -1;
}

const int N = 1e6 + 50;
int f[N], ans[N];

int main(int argc, const char * argv[]) {
    int n; scanf("%d", &n);
    vector<int> a(1 << 18), b;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        f[x] = 1;
    }
    for (int i = 0; i < (1 << 18); i++) a[i] = f[i];
    b = a;
    ans[1] = qmax(b);
    for (int i = 2; i < 20; i++) {
        b = Xor(b, a);
        ans[i] = qmax(b);
    }
    for (int i = 20; i <= n; i++) {
        ans[i] = ans[i - 2];
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", ans[i], i == n ? '\n' : ' ');
    }
    return 0;
}

子集卷积

题目：P6097 【模板】子集卷积
题目大意：

给定两个长度为 2^n 的序列 a_0,a_1,\cdots,a_{2^n-1} 和 b_0,b_1,\cdots,b_{2^n-1}，你需要求出一个序列 c_0,c_1,\cdots,c_{2^n-1}，其中 c_k 满足：

c_k=\sum_{\substack{{i \And j=0}\cr{i \mid j=k}}} a_i b_j

答案对 10^9+9 取模。

#include <bits/stdc++.h>
using namespace std;
#define pct(x) __builtin_popcount(x)
const int P = 1e9 + 9;

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += P);
}
void FWTor(vector<int> &a, bool rev) {
    int n = (int)a.size();
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
        for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
            if (!rev) add(a[i + j + m], a[i + j]);
            else sub(a[i + j + m], a[i + j]);
        }
    }
}
vector<int> Subset(vector<int> &a1, vector<int> &a2, int lim) {
    int n = (int)max(a1.size(), a2.size());
    vector<int> ret(n);
    vector< vector<int> > a(lim + 1, vector<int>(n)), b = a, A = a;
    for (int i = 0; i < n; i++) {
        a[pct(i)][i] = a1[i]; b[pct(i)][i] = a2[i];
    }
    for (int i = 0; i <= lim; i++) {
        FWTor(a[i], false); FWTor(b[i], false);
    }
    for (int i = 0; i <= lim; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k < n; k++) {
                (A[i][k] += 1LL * a[j][k] * b[i-j][k] % P) %= P;
            }
        }
    }
    for (int i = 0; i <= lim; i++) FWTor(A[i], true);
    for (int i = 0; i < n; i++) ret[i] = A[pct(i)][i];
    return ret;
}

int main() {
    int lim; scanf("%d", &lim);
    int n = 1 << lim;
    vector<int> a(n), b(n), res;
    for (int &x : a) scanf("%d", &x);
    for (int &x : b) scanf("%d", &x);
    res = Subset(a, b, lim);
    for (int x : res) printf("%d ", x); putchar(10);
    return 0;
}

倍增子集卷积

例题：hdu6851（2020hdu多校第七场 1008）

题目大意：

给 n 个法术，每种法术需要一个物品的集合，每个物品只能被使用一次；一个可同时使用的法术的集合的权值为各法术权值的乘积。
共 q 次询问，问恰好使用物品集合为 x 的所有法术集合的权值和。

解题思路：

如果规定每个物品集合至多有两个法术，就是裸的子集卷积了。暴力做 21 次全子集卷积一定会超时。考虑优化：

由于最高位相同的法术不可能同时存在，即不可能卷积在一起，我们把物品按照最高位分组再分别卷积起来。

复杂度分析：O\left(\sum_{i=1}^{n}i^2\cdot 2^i \right)=O\left(i^n\cdot 2^n \right)，且常数小于 2。

#include <bits/stdc++.h>
using namespace std;
#define pct(x) __builtin_popcount(x)
const int P = 998244353;

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += P);
}
void FWTor(vector<int> &a, bool rev) {
    int n = (int)a.size();
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
        for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
            if (!rev) add(a[i + j + m], a[i + j]);
            else sub(a[i + j + m], a[i + j]);
        }
    }
}

vector<int> Subset(vector<int> &a1, vector<int> &a2, int lim) {
    int n = 1 << lim;
    vector<int> ret(n);
    vector< vector<int> > a(lim + 1, vector<int>(n)), b = a, A = a;
    for (int i = 0; i < n; i++) {
        a[pct(i)][i] = a1[i]; b[pct(i)][i] = a2[i];
    }
    for (int i = 0; i <= lim; i++) {
        FWTor(a[i], false); FWTor(b[i], false);
    }
    for (int i = 0; i <= lim; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k < n; k++) {
                (A[i][k] += 1LL * a[j][k] * b[i - j][k] % P) %= P;
            }
        }
    }
    for (int i = 0; i <= lim; i++) FWTor(A[i], true);
    for (int i = 0; i < n; i++) ret[i] = A[pct(i)][i];
    return ret;
}
vector<int> conv(vector<int> &a) {
    int Base = 21, Len = 1 << Base;
    vector<int> ret(Len); ret[0] = 1;
    for (int n = 0; n < Base; n++) {
        int ful = 1 << n;
        auto A = vector<int>(ret.begin(), ret.begin() + ful);
        auto B = vector<int>(a.begin() + ful, a.begin() + ful * 2);
        auto C = Subset(A, B, n);
        for (int i = ful; i < ful * 2; i++) {
            ret[i] = C[i - ful];
        }
    }
    return ret;
}

int n, m;

int main(int argc, const char * argv[]) {
    scanf("%d", &n); int lim = 21;
    vector<int> a(1 << lim), ans;
    for (int i = 1, p, b; i <= n; i++) {
        scanf("%d%d", &p, &b);
        (a[b] += p) %= P;
    }
    ans = conv(a);
    scanf("%d", &m);
    for (int i = 1, x; i <= m; i++) {
        scanf("%d", &x);
        printf("%d\n", ans[x]);
    }
    return 0;
}
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇