牛客网暑期ACM多校训练营(第九场)A.Circulant Matrix(FWT)
我们首先观察一下这几个等式
之后对于bi易得这样一则等式
那么稍作转化我们便可以得到下式
这个东西不就是FWT吗
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MOD=1e9+7; const int inv2=5e8+4; int powmod(int a,int b) { int ans=1; while(b) { if(b&1) ans=(1ll*ans*a)%MOD; a=(1ll*a*a)%MOD; b>>=1; } return ans; } void FWT_xor(int *a,int n,int opt) { while((n&-n)!=n) n+=(n&-n); for(int i=1; i<n; i<<=1) for(int p=i<<1,j=0; j<n; j+=p) for(int k=0; k<i; ++k) { ll X=a[j+k],Y=a[i+j+k]; a[j+k]=(X+Y)%MOD; a[i+j+k]=(X+MOD-Y)%MOD; if(opt==-1) a[j+k]=1ll*a[j+k]*inv2%MOD,a[i+j+k]=1ll*a[i+j+k]*inv2%MOD; } } int a[1<<20]; int b[1<<20]; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) scanf("%d",&b[i]); FWT_xor(a,n,1),FWT_xor(b,n,1); for(int i=0;i<n;i++) a[i]=1ll*b[i]*powmod(a[i],MOD-2)%MOD; FWT_xor(a,n,-1); for(int i=0;i<n;i++) printf("%d\n",(a[i])%MOD); }
发表评论