快速沃尔什变换

题目描述

给定长度为\(2^n\)两个序列\(A,B\)，设\(C_i=\sum_{j\oplus k}A_jB_k\)分别当\(\oplus\)是or,and,xor时求出C

输入输出格式

输入格式：

第一行一个数n。第二行\(2^n\)个数\(A_0..A_{2^n-1}\)第三行\(2^n\)个数\(B_0..B_{2^n-1}\)

输出格式：

三行每行\(2^n\)个数，分别代表\(\oplus\)是or,and,xor时\(C_0..C_{2^n-1}\)的值\(\bmod\ 998244353\)

输入输出样例

输入样例#1：

2

2 4 6 8

1 3 5 7

输出样例#1：

2 22 46 250

88 64 112 56

100 92 68 60

说明

\(n\le 17\)。

题解

2015吕凯风论文和2013王迪论文。

快速莫比乌斯变换

这个只能用来做集合并和与卷积，但是容易理解。

我通过《浅谈容斥原理》找到了另一种形式：

那么通过相同的手段，就可以做集合交卷积。

快速沃尔什变换

这个理论有点复杂，现场推是不可能的，所以背版子吧。

还有类似FFT的实现，不过我反而觉得难写许多。

代码总结

and是超集和变换（高维后缀和）。逆变换是超集差变换。
or是子集和变换（高维前缀和）。逆变换是子集差变换。
xor是蝴蝶变换。逆变换是最后除以长度。

void FAT(poly&a,int dir){ // and -> superset

	int lim=a.size(),len=log2(lim);

	for(int j=0;j<len;++j)

		for(int i=0;i<lim;++i)if(~i>>j&1)

			a[i]=add(a[i],dir==1?a[i|1<<j]:mod-a[i|1<<j]);

}

void FOT(poly&a,int dir){ // or -> subset

	int lim=a.size(),len=log2(lim);

	for(int j=0;j<len;++j)

		for(int i=0;i<lim;++i)if(i>>j&1)

			a[i]=add(a[i],dir==1?a[i^1<<j]:mod-a[i^1<<j]);

}

void FXT(poly&a,int dir){ // xor

	int lim=a.size(),len=log2(lim);

	for(int j=0;j<len;++j)

		for(int i=0;i<lim;++i)if(~i>>j&1){

			int l=a[i],r=a[i|1<<j];

			a[i]=add(l,r),a[i|1<<j]=add(l,mod-r);

		}

	if(dir==-1){

		int ilim=fpow(lim,mod-2);

		for(int i=0;i<lim;++i) a[i]=mul(a[i],ilim);

	}

}

int main(){

	int len=read<int>(),lim=1<<len;

	poly f(lim),g(lim);

	for(int i=0;i<lim;++i) read(f[i]);

	for(int i=0;i<lim;++i) read(g[i]);

	// or

	poly a=f,b=g;

	FOT(a,1),FOT(b,1);

	for(int i=0;i<lim;++i) a[i]=mul(a[i],b[i]);

	FOT(a,-1);

	for(int i=0;i<lim;++i) printf("%d%c",a[i]," \n"[i==lim-1]);

	// and

	a=f,b=g;

	FAT(a,1),FAT(b,1);

	for(int i=0;i<lim;++i) a[i]=mul(a[i],b[i]);

	FAT(a,-1);

	for(int i=0;i<lim;++i) printf("%d%c",a[i]," \n"[i==lim-1]);

	// xor

	a=f,b=g;

	FXT(a,1),FXT(b,1);

	for(int i=0;i<lim;++i) a[i]=mul(a[i],b[i]);

	FXT(a,-1);

	for(int i=0;i<lim;++i) printf("%d%c",a[i]," \n"[i==lim-1]);

	return 0;

}

巴特西

LG4717 【模板】快速沃尔什变换

快速沃尔什变换

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1：

输出样例#1：

说明

题解

快速莫比乌斯变换

快速沃尔什变换

代码总结

最新文章

热门文章