题目描述
给定 \(n\) 和长度为 \(2^n\) 的数列 \(a_{0},a_{1}...a_{2^n-1}\) 和 \(b_{0},b_1...b_{2^n-1}\)，保证每个元素的值属于 \([0,3]\)
生成序列 \(c\)，对于 \(c_i\)，有：
\[c_i=\sum_{j|k=i,j\&k=0} a_j\times b_k \]求 \(c_{0},c_1...c_{2^n-1}\)，答案对 \(4\) 取模。
\(n\le 21\)，时限 \(\rm 1s\)
题解
貌似是一个FWT卷积的形式，但是有\(j\&k=0\)。
可以换个角度思考这样的操作有什么性质。
于是可以得出：当\(popcount(j)+popcount(k)=popcount(i)\)时，\(c_i=\sum_{j|k=i} a_j\times b_k\)
那么可以对popcount不同的数分别操作，复杂度\(n^2 2^n\)。
还有一个题目条件没有用到，数在模4意义下操作。
于是可以将\(a_j\)变换为\(a_j\times 4^{popcount(j)}\),b同理，最终的\(c_i\)再模\(4^{popcount(i)}\)就可以刚好得到答案。
妙啊！！
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=2100010;
int n;
unsigned int a[N],b[N],c[N];
char s[N];
unsigned int fw[30];
unsigned int cal(int x){
int ansn=0;
while(x)ansn+=(x%2==1),x/=2;
return fw[ansn];
}
void fwt(unsigned int *f,int tag){
for(int k=1;k<=n;k*=2){
for(int i=0;i<n;i+=k*2){
for(int j=0;j<k;j++)if(i+j+k<n)f[i+j+k]+=f[i+j]*tag;
}
}
return ;
}
signed main(){
n=(1<<rd());
scanf("%s",s);
for(int i=0;i<n;i++)a[i]=s[i]-'0';
scanf("%s",s);
for(int i=0;i<n;i++)b[i]=s[i]-'0';
fw[0]=1;
for(int i=1;i<=21;i++)fw[i]=fw[i-1]*4;
for(int i=0;i<n;i++)a[i]*=cal(i),b[i]*=cal(i);
fwt(a,1),fwt(b,1);
for(int i=0;i<n;i++)c[i]=a[i]*b[i];
fwt(c,-1);
// for(int i=0;i<n;i++)cout<<c[i]<<" ";
// cout<<"\n";
for(int i=0;i<n;i++)c[i]=c[i]/cal(i)%4;
for(int i=0;i<n;i++)cout<<c[i];
return 0;
}