P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT / FWT)题解

P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT / FWT)

题目描述

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

$$C_i=\sum _{j\oplus k=i}{A}_j\times B_k$$

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

输入格式

第一行，一个整数 $n$。
第二行，$2^n$ 个数 $A_0,A_1,\dots ,A_{2^n-1}$。
第三行，$2^n$ 个数 $B_0,B_1,\dots ,B_{2^n-1}$。

输出格式

三行，每行 $2^n$ 个数，分别代表 $\oplus$ 是 or, and, xor 时 $C_0,C_1,\dots ,C_{2^n-1}$ 的值 $\mathrm{mod}998244353$。

输入输出样例 #1

输入 #1

2
2 4 6 8
1 3 5 7

输出 #1

2 22 46 250
88 64 112 56
100 92 68 60

说明/提示

$1\le n\le 17$。

思路

模板题，直接写即可。

代码见下

#include<bits/stdc++.h>
using namespace std;
long long n,m,aa[200005],bb[200005],a[200005],b[200005];
const long long mod=998244353;
void or1(long long *f,long long x){
for(int o=2,k=1;o<=n;o*=2,k*=2){
for(int i=0;i<=n–1;i+=o){
for(int j=0;j<=k–1;j++){
f[i+j+k]=(f[i+j+k]+f[i+j]*x)%mod;
}
}
}
return ;
}
void and1(long long *f,long long x){
for(int o=2,k=1;o<=n;o*=2,k*=2){
for(int i=0;i<=n–1;i+=o){
for(int j=0;j<=k–1;j++){
f[i+j]=(f[i+j]+f[i+j+k]*x)%mod;
}
}
}
return ;
}
void xor1(long long *f,long long x){
for(int o=2,k=1;o<=n;o*=2,k*=2){
for(int i=0;i<=n–1;i+=o){
for(int j=0;j<=k–1;j++){
f[i+j]=(f[i+j]+f[i+j+k])%mod;
f[i+j+k]=(f[i+j]–f[i+j+k]–f[i+j+k]+mod*2)%mod;
f[i+j]=(f[i+j]*x)%mod;
f[i+j+k]=(f[i+j+k]*x)%mod;
}
}
}
return ;
}
int main(){
cin>>m;
n=pow(2,m);
for(int i=0;i<=n–1;i++){
cin>>aa[i];
}
for(int i=0;i<=n–1;i++){
cin>>bb[i];
}
for(int i=0;i<=n–1;i++){
a[i]=aa[i];
b[i]=bb[i];
}
or1(a,1);
or1(b,1);
for(int i=0;i<=n–1;i++){
a[i]=(a[i]*b[i])%mod;
}
or1(a,mod–1);
for(int i=0;i<=n–1;i++){
cout<<a[i]<<" ";
}
cout<<endl;
for(int i=0;i<=n–1;i++){
a[i]=aa[i];
b[i]=bb[i];
}
and1(a,1);
and1(b,1);
for(int i=0;i<=n–1;i++){
a[i]=(a[i]*b[i])%mod;
}
and1(a,mod–1);
for(int i=0;i<=n–1;i++){
cout<<a[i]<<" ";
}
cout<<endl;
for(int i=0;i<=n–1;i++){
a[i]=aa[i];
b[i]=bb[i];
}
xor1(a,1);
xor1(b,1);
for(int i=0;i<=n–1;i++){
a[i]=(a[i]*b[i])%mod;
}
xor1(a,mod/2+1);
for(int i=0;i<=n–1;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}