[洛谷P4717]【模板】快速沃尔什变换

题目大意：给定多项式$A$和$B$，求$C$满足：

$$
C_n=\sum\limits_{x\oplus y=n}A_xB_y
$$

其中$\oplus$为位运算（$or,and,xor​$）

题解：$FWT$，可以见这篇博客

卡点：无

C++ Code：

#include <algorithm>

#include <cstdio>

#define maxn 262144

const int mod = 998244353;

namespace Math {

	inline int pw(int base, int p) {

		static int res;

		for (res = 1; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;

		return res;

	}

	inline int inv(int x) { return pw(x, mod - 2); }

}

inline void reduce(int &x) { x += x >> 31 & mod; }

inline void clear(register int *l, const int *r) {

	if (l >= r) return ;

	while (l != r) *l++ = 0;

}

int __n, n, lim;

int A[maxn], B[maxn], C[maxn], D[maxn];

inline void FWT_OR(int *A) {

	for (register int mid = 1; mid < lim; mid <<= 1)

		for (register int i = 0; i < lim; i += mid << 1)

			for (register int j = 0; j < mid; ++j) reduce(A[i + j + mid] += A[i + j] - mod);

}

inline void IFWT_OR(int *A) {

	for (register int mid = 1; mid < lim; mid <<= 1)

		for (register int i = 0; i < lim; i += mid << 1)

			for (register int j = 0; j < mid; ++j) reduce(A[i + j + mid] -= A[i + j]);

}

inline void FWT_AND(int *A) {

	for (register int mid = 1; mid < lim; mid <<= 1)

		for (register int i = 0; i < lim; i += mid << 1)

			for (register int j = 0; j < mid; ++j) reduce(A[i + j] += A[i + j + mid] - mod);

}

inline void IFWT_AND(int *A) {

	for (register int mid = 1; mid < lim; mid <<= 1)

		for (register int i = 0; i < lim; i += mid << 1)

			for (register int j = 0; j < mid; ++j) reduce(A[i + j] -= A[i + j + mid]);

}

inline void FWT_XOR(int *A, const int op = 1) {

	for (register int mid = 1; mid < lim; mid <<= 1)

		for (register int i = 0; i < lim; i += mid << 1)

			for (register int j = 0; j < mid; ++j) {

				const int X = A[i + j], Y = A[i + j + mid];

				reduce(A[i + j] += Y - mod), reduce(A[i + j + mid] = X - Y);

			}

	if (!op) {

		const int ilim = Math::inv(lim);

		for (register int *i = A; i != A + lim; ++i) *i = static_cast<long long> (*i) * ilim % mod;

	}

}

int main() {

	scanf("%d", &__n); n = Math::pw(2, __n);

	for (int i = 0; i < n; ++i) scanf("%d", A + i);

	for (int i = 0; i < n; ++i) scanf("%d", B + i);

	lim = n;

	std::copy(A, A + n, C); clear(C + n, C + lim);

	std::copy(B, B + n, D); clear(D + n, D + lim);

	FWT_OR(C), FWT_OR(D);

	for (int i = 0; i < lim; ++i) C[i] = static_cast<long long> (C[i]) * D[i] % mod;

	IFWT_OR(C);

	for (int i = 0; i < n; ++i) printf("%d ", C[i]); puts("");

	std::copy(A, A + n, C); clear(C + n, C + lim);

	std::copy(B, B + n, D); clear(D + n, D + lim);

	FWT_AND(C), FWT_AND(D);

	for (int i = 0; i < lim; ++i) C[i] = static_cast<long long> (C[i]) * D[i] % mod;

	IFWT_AND(C);

	for (int i = 0; i < n; ++i) printf("%d ", C[i]); puts("");

	std::copy(A, A + n, C); clear(C + n, C + lim);

	std::copy(B, B + n, D); clear(D + n, D + lim);

	FWT_XOR(C), FWT_XOR(D);

	for (int i = 0; i < lim; ++i) C[i] = static_cast<long long> (C[i]) * D[i] % mod;

	FWT_XOR(C, 0);

	for (int i = 0; i < n; ++i) printf("%d ", C[i]); puts("");

	return 0;

}