子集卷积， \(len\le 2^{21},0\le a[i],b[i]\le 3,ans\%4\)
即对于 \(i\in[0,2^n-1]\) 求出
\[(\sum_{j|k=i,j\&k=0}a[j]\times b[k])\mod 4 \]看到这题 \(5min\) 莽了个子集卷积上去，MLE on 1
哦， \(64MB\) ，那就压位！
写挂了，调了一个下午，终于 调出来了！
然后 TLE on 7
好了，彻底放弃暴力过去的方法
\(\color{black}{\texttt{z}}\color{red}{\texttt{houakngyang}}\) 告诉我可以 \(O(n\log n)\) ，我深深地感到了我的弱小
具体做法是这样的：设 \(cnt_i\) 表示 \(i\) 的二进制中 \(1\) 的个数
令 \(a_i=2^{2*cnt_i}*s_i\) （\(s\) 是输入的字符串）
\(b_i\) 同理
然后，直接FWT把两个东西或起来，乘上 \(\dfrac{1}{2^{2*cnt_i}}\) 输出 。
为啥这是对的？
\(\color{black}{\texttt{z}}\color{red}{\texttt{houakngyang}}\) 告诉我：考虑当 \(k=i|j\) 时，\(cnt_i+cnt_j\ge cnt_k\) 。
这有啥用啊？
当 \(i\&j\not=0\) 时，\(\dfrac{cnt_i+cnt_j}{2*cnt_k}>0\) ，\(4^{\frac{cnt_i+cnt_j}{2*cnt_k}}\mod 4=0\) ，不产生贡献
否则产生的贡献恰好是题目所求的。
大结论题。。。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f?x:-x;
}
int rdc(){
char ch=getchar();
while(!isdigit(ch))ch=getchar();
return ch-'0';
}
const int N=1<<21;
int n,m;
LL a[N],b[N];
void fwt(LL*a,int op){
for(int i=1;i<m;i<<=1)
for(int j=0;j<m;j+=i<<1)
for(int k=0;k<i;++k)
a[i+j+k]+=a[j+k]*op;
}
signed main(){
m=(1<<(n=read()));
for(int i=0;i<m;++i)a[i]=(1ll<<(__builtin_popcount(i)<<1))*rdc();
for(int i=0;i<m;++i)b[i]=(1ll<<(__builtin_popcount(i)<<1))*rdc();
fwt(a,1),fwt(b,1);
for(int i=0;i<m;++i)a[i]*=b[i];
fwt(a,-1);
for(int i=0;i<m;++i)putchar('0'+((a[i]>>(__builtin_popcount(i)<<1))&3));
puts("");
return 0;
}