原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1773.html
题目传送门 - 51Nod1773
题意
给定一个长度为 $2^n$ 的序列，第 $i$ 项为 $f_{i-1}$ 。
现在让你做 $T$ 次这样的运算：($i\in[0,2^n)$)
$$f^{\prime}_i=f_i+\sum_{j=0}^{n-1} f_{i\ {\rm XOR} \ 2^j}$$
输出最终的 $f$ 序列。
题解
构造转移多项式 $g$ 。使得 $g_0=1,g_{2^i}=1$ 。
答案为 $f * g^T$ ，其中 $*$ 为异或卷积 。
代码
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x;
}
void write(int x){
if (x>9)
write(x/10);
putchar(x%10+'0');
}
const int N=1<<20,mod=1e9+7,inv2=5e8+4;
int n,k,d,a[N],b[N];
int Pow(int x,int y){
int ans=1;
for (;y;y>>=1,x=1LL*x*x%mod)
if (y&1)
ans=1LL*ans*x%mod;
return ans;
}
void FWT(int a[],int n,int flag){
for (int d=1;d<n;d<<=1)
for (int i=0;i<n;i+=(d<<1))
for (int j=0;j<d;j++){
int &L=a[i+j],&R=a[i+j+d];
int x=a[i+j],y=a[i+j+d];
L=x+y;
if (L>=mod)
L-=mod;
R=x-y;
if (R<0)
R+=mod;
if (flag==-1){
L=1LL*L*inv2%mod;
R=1LL*R*inv2%mod;
}
}
}
int main(){
d=read(),k=read(),n=1<<d;
for (int i=0;i<n;i++)
a[i]=read();
memset(b,0,sizeof b);
b[0]=1;
for (int i=0;i<d;i++)
b[1<<i]=1;
FWT(a,n,1),FWT(b,n,1);
for (int i=0;i<n;i++)
a[i]=1LL*a[i]*Pow(b[i],k)%mod;
FWT(a,n,-1);
for (int i=0;i<n;i++)
write(a[i]),putchar(' ');
return 0;
}