【模板】快速沃尔时变换

一份优秀的题解

以及一份常数很大的代码：

#include <iostream>
#include <cstring>
namespace Fread {
	const int Fread_size = (1<<18);
	char Fread_buf[Fread_size];
	char *Fread_h, *Fread_t;
	char getchar() {
		if(Fread_h == Fread_t) {
			Fread_t = (Fread_h = Fread_buf)+fread(Fread_buf,1,Fread_size,stdin);
			if(Fread_h == Fread_t) return '\n';
		}
		return *Fread_h++;
	}
}
#define getchar Fread::getchar
char _tc;
bool _sg;
template<typename Tec>
void get_int(Tec &_aim) {
	_sg = false, _tc = getchar(), _aim = 0;
	for(;!isdigit(_tc);_tc = getchar()) 
		if(_tc == '-') _sg = true;
	for(;isdigit(_tc);_tc = getchar()) 
		_aim = (_aim<<1)+(_aim<<3)+(_tc^48);
	if(_sg) {
		_aim = ~_aim;
		++_aim;
	}
}
const int moyn = 998244353;
const int N = 150005;
int n;
void FWT_OR(int *a,long long operation) {
	for(int p_1 = 1, p_2 = 2;p_2 <= n;p_1 <<= 1, p_2 <<= 1) 
		for(int i = 0;i < n;i += p_2) 
			for(int j = 0;j < p_1;++j) 
				a[i+j+p_1] = (a[i+j+p_1]+a[i+j]*operation)%moyn;
}
void FWT_AND(int *a,long long operation) {
	for(int p_1 = 1, p_2 = 2;p_2 <= n;p_1 <<= 1, p_2 <<= 1) 
		for(int i = 0;i < n;i += p_2) 
			for(int j = 0;j < p_1;++j) 
				a[i+j] = (a[i+j]+a[i+j+p_1]*operation)%moyn;
}
void FWT_XOR(int *a,long long operation) {
	for(int p_1 = 1, p_2 = 2;p_2 <= n;p_1 <<= 1, p_2 <<= 1) 
		for(int i = 0;i < n;i += p_2) 
			for(int j = 0;j < p_1;++j) {
				int x = a[i+j], y = a[i+j+p_1];
				a[i+j] = operation*(x+y)%moyn;
				a[i+j+p_1] = operation*(x-y+moyn)%moyn;
			}
}
int a[N], b[N], c[N];
int copy_a[N], copy_b[N];
int main() {
	scanf("%d",&n);
	n = 1<<n;
	for(int i = 0;i < n;++i) {
		get_int(a[i]);
		a[i] %= moyn;
	}
	for(int i = 0;i < n;++i) {
		get_int(b[i]);
		b[i] %= moyn;
	}
	memcpy(copy_a,a,(n+1)*sizeof(int));
	memcpy(copy_b,b,(n+1)*sizeof(int));
	FWT_OR(copy_a,1);
	FWT_OR(copy_b,1);
	for(int i = 0;i < n;++i) 
		c[i] = 1ll*copy_a[i]*copy_b[i]%moyn;
	FWT_OR(c,moyn-1);
	for(int i = 0;i < n;++i) 
		printf("%d ",c[i]);
	putchar(10);

	memcpy(copy_a,a,(n+1)*sizeof(int));
	memcpy(copy_b,b,(n+1)*sizeof(int));
	FWT_AND(copy_a,1);
	FWT_AND(copy_b,1);
	for(int i = 0;i < n;++i) 
		c[i] = 1ll*copy_a[i]*copy_b[i]%moyn;
	FWT_AND(c,moyn-1);
	for(int i = 0;i < n;++i) 
		printf("%d ",c[i]);
	putchar(10);

	memcpy(copy_a,a,(n+1)*sizeof(int));
	memcpy(copy_b,b,(n+1)*sizeof(int));
	FWT_XOR(copy_a,1);
	FWT_XOR(copy_b,1);
	for(int i = 0;i < n;++i) 
		c[i] = 1ll*copy_a[i]*copy_b[i]%moyn;
	FWT_XOR(c,998244354/2);
	for(int i = 0;i < n;++i) 
		printf("%d ",c[i]);
	putchar(10);
	return 0;
}