【题目分析】

    位运算下的卷积问题。

    FWT直接做。

    但还是不太民白，发明者要承担泽任的。

【代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define ll long long#define maxn 100005int pr[maxn],ispr[maxn],top,n,m,a[maxn],inv,len;const int md=1e9+7;void FWT(int l,int r){	if (l==r) return ;	int mid=l+r>>1;	FWT(l,mid); FWT(mid+1,r);	for (int i=l,j=mid+1;i<=mid;++i,++j)	{		int x=(a[i]+a[j])%md;		a[i]=(a[i]-a[j]+md)%md;		a[j]=x;	}}int pow(int a,int b){	int ret=1;	while (b)	{		if (b&1) ret=(ll)ret*a%md;		a=(ll)a*a%md;		b>>=1;	}	return ret;}void DWT(int l,int r){	if (l==r) return;	int mid=l+r>>1;	for (int i=l,j=mid+1;i<=mid;++i,++j)	{		int x=(ll)(a[j]-a[i]+md)*inv%md;		a[i]=(ll)(a[i]+a[j])*inv%md;		a[j]=x;	}	DWT(l,mid); DWT(mid+1,r);}int main(){	inv=pow(2,md-2);	for (int i=2;i