%%%%%%%%
by NaCly_Fish @ 2019-01-23 20:49:58
%%%%%%%%
by RiverFun @ 2019-01-23 20:53:48
%%%%%%%%
by 无意识躺枪人 @ 2019-01-23 20:54:14
tql!!!
by abs001 @ 2019-01-23 20:55:41
如今的自称蒟蒻都是红名,我一个蓝名连自称蒟蒻的资格都没有了,呜呜呜呜...
by AFO蒟蒻选手 @ 2019-01-23 20:57:13
%%%%%%%%
by Tsumi @ 2019-01-23 20:58:46
抄 `yyb` 模板的蒟蒻来了![](https://cdn.luogu.com.cn/upload/pic/49456.png)
```cpp
#include<bits/stdc++.h>
#define MAXN 1<<17
using namespace std;
const int Mod=998244353;
int n,len,a[MAXN],b[MAXN],c[MAXN],inv2;
int QuickPow(int x,int y)
{
int res=1;
while(y)
{
if(y&1) res=1ll*res*x%Mod;
x=1ll*x*x%Mod;
y>>=1;
}
return res;
}
void FWTOr(int *f,int opt)
{
for(int i=1;i<len;i<<=1)
{
int p=i<<1;
for(int j=0;j<len;j+=p)
{
for(int k=0;k<i;k++)
{
if(opt==1) f[i+j+k]=(f[j+k]+f[i+j+k])%Mod;
else f[i+j+k]=(f[i+j+k]-f[j+k]+Mod)%Mod;
}
}
}
}
void FWTAnd(int *f,int opt)
{
for(int i=1;i<len;i<<=1)
{
int p=i<<1;
for(int j=0;j<len;j+=p)
{
for(int k=0;k<i;k++)
{
if(opt==1) f[j+k]=(f[j+k]+f[i+j+k])%Mod;
else f[j+k]=(f[j+k]-f[i+j+k]+Mod)%Mod;
}
}
}
}
void FWTXor(int *f,int opt)
{
for(int i=1;i<len;i<<=1)
{
int p=i<<1;
for(int j=0;j<len;j+=p)
{
for(int k=0;k<i;k++)
{
int x=f[j+k],y=f[i+j+k];
f[j+k]=(x+y)%Mod;
f[i+j+k]=(x-y+Mod)%Mod;
if(!~opt)
{
f[j+k]=1ll*f[j+k]*inv2%Mod;
f[i+j+k]=1ll*f[i+j+k]*inv2%Mod;
}
}
}
}
}
signed main()
{
inv2=QuickPow(2,Mod-2);
scanf("%d",&n);
len=1<<n;
for(int i=0;i<len;i++) scanf("%d",&a[i]);
for(int i=0;i<len;i++) scanf("%d",&b[i]);
FWTOr(a,1);
FWTOr(b,1);
for(int i=0;i<len;i++) c[i]=1ll*a[i]*b[i]%Mod;
FWTOr(a,-1);
FWTOr(b,-1);
FWTOr(c,-1);
for(int i=0;i<len;i++) printf("%d ",c[i]);
puts("");
FWTAnd(a,1);
FWTAnd(b,1);
for(int i=0;i<len;i++) c[i]=1ll*a[i]*b[i]%Mod;
FWTAnd(a,-1);
FWTAnd(b,-1);
FWTAnd(c,-1);
for(int i=0;i<len;i++) printf("%d ",c[i]);
puts("");
FWTXor(a,1);
FWTXor(b,1);
for(int i=0;i<len;i++) c[i]=1ll*a[i]*b[i]%Mod;
FWTXor(c,-1);
for(int i=0;i<len;i++) printf("%d ",c[i]);
return 0;
}
```
by vocaloid @ 2019-01-23 21:03:08
orz Fakeration.您太假了qwq
$qwq^{qwq^{qwq^{qwq}}}_{qwq_{qwq_{qwq}}}$
$$fake$$
---
~~其实我不会fwt啊2333~~
by hehelego @ 2019-01-23 21:06:38