洛谷P4717 【模板】快速沃尔什变换(FWT)
程序员文章站
2022-04-14 21:51:34
题意 "题目链接" Sol 背板子背板子 cpp include using namespace std; const int MAXN = (1 '9') {if(c == ' ') f = 1; c = getchar();} while(c = '0' && c = mod ? x + y m ......
题意
sol
背板子背板子
#include<bits/stdc++.h> using namespace std; const int maxn = (1 << 17) + 10, mod = 998244353, inv2 = 499122177; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, a[maxn], b[maxn], c[maxn]; int add(int x, int y) { if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y; } int mul(int x, int y) { return 1ll * x * y % mod; } void fwtor(int *a, int opt) { for(int mid = 1; mid < n; mid <<= 1) for(int r = mid << 1, j = 0; j < n; j += r) for(int k = 0; k < mid; k++) if(opt == 1) a[j + k + mid] = add(a[j + k], a[j + k + mid]); else a[j + k + mid] = add(a[j + k + mid], -a[j + k]); } void fwtand(int *a, int opt) { for(int mid = 1; mid < n; mid <<= 1) for(int r = mid << 1, j = 0; j < n; j += r) for(int k = 0; k < mid; k++) if(opt == 1) a[j + k] = add(a[j + k], a[j + k + mid]); else a[j + k] = add(a[j + k], -a[j + k + mid]); } void fwtxor(int *a, int opt) { for(int mid = 1; mid < n; mid <<= 1) for(int r = mid << 1, j = 0; j < n; j += r) for(int k = 0; k < mid; k++) { int x = a[j + k], y = a[j + k + mid]; if(opt == 1) a[j + k] = add(x, y), a[j + k + mid] = add(x, -y); else a[j + k] = mul(add(x, y), inv2), a[j + k + mid] = mul(add(x, -y), inv2); } } int main() { n = 1 << (read()); for(int i = 0; i < n; i++) a[i] = read(); for(int i = 0; i < n; i++) b[i] = read(); fwtor(a, 1); fwtor(b, 1); for(int i = 0; i < n; i++) c[i] = mul(a[i], b[i]); fwtor(c, -1); fwtor(a, -1); fwtor(b, -1); for(int i = 0; i < n; i++) printf("%d ", c[i]); puts(""); fwtand(a, 1); fwtand(b, 1); for(int i = 0; i < n; i++) c[i] = mul(a[i], b[i]); fwtand(c, -1); fwtand(a, -1); fwtand(b, -1); for(int i = 0; i < n; i++) printf("%d ", c[i]); puts(""); fwtxor(a, 1); fwtxor(b, 1); for(int i = 0; i < n; i++) c[i] = mul(a[i], b[i]); fwtxor(c, -1); fwtxor(a, -1); fwtxor(b, -1); for(int i = 0; i < n; i++) printf("%d ", c[i]); return 0; }