链接：https://www.nowcoder.com/acm/contest/147/A
来源：牛客网
The first line contains an integer, which is n.
The second line contains n integers, which are the array a.
The third line contains n integers, which are the array b.
1 <= n <= 262144
p = 1000000007
0 <= a[i] < p
0 <= b[i] < p
The output should contains n lines.
The i-th(index from 0) line should contain x[i].
x[i] is an integer, and should satisfy 0 <= x[i] < p.
4 1 10 100 1000 1234 2143 3412 4321
3 2 1
解析 给出已知A b 求 x
上式可以转化成由于 i^j^j=i
所以原式等式直接套fwt_xor 板子
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,n) for (int i=a;i<n;i++) 4 #define per(i,a,n) for (int i=n-1;i>=a;i--) 5 #define pb push_back 6 #define mp make_pair 7 #define all(x) (x).begin(),(x).end() 8 #define fi first 9 #define se second 10 #define SZ(x) ((int)(x).size()) 11 typedef vector<int> VI; 12 typedef long long ll; 13 typedef pair<int,int> PII; 14 const ll mod=1000000007; 15 const int maxn = 3e6+10; 16 ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} 17 // head 18 19 int a[maxn],b[maxn]; 20 void FWT_or(int *a,int N,int opt) 21 { 22 for(int i=1;i<N;i<<=1) 23 for(int p=i<<1,j=0;j<N;j+=p) 24 for(int k=0;k<i;++k) 25 if(opt==1)a[i+j+k]=(a[j+k]+a[i+j+k])%mod; 26 else a[i+j+k]=(a[i+j+k]+mod-a[j+k])%mod; 27 } 28 void FWT_and(int *a,int N,int opt) 29 { 30 for(int i=1;i<N;i<<=1) 31 for(int p=i<<1,j=0;j<N;j+=p) 32 for(int k=0;k<i;++k) 33 if(opt==1)a[j+k]=(a[j+k]+a[i+j+k])%mod; 34 else a[j+k]=(a[j+k]+mod-a[i+j+k])%mod; 35 } 36 void FWT_xor(int *a,int N,int opt) //opt=1 正变换 opt=-1 逆变换 37 { 38 ll inv2=powmod(2,mod-2); 39 for(int i=1;i<N;i<<=1) 40 for(int p=i<<1,j=0;j<N;j+=p) 41 for(int k=0;k<i;++k) 42 { 43 int X=a[j+k],Y=a[i+j+k]; 44 a[j+k]=(X+Y)%mod;a[i+j+k]=(X+mod-Y)%mod; 45 if(opt==-1)a[j+k]=1ll*a[j+k]*inv2%mod,a[i+j+k]=1ll*a[i+j+k]*inv2%mod; 46 } 47 } 48 int main() 49 { 50 int n; 51 scanf("%d",&n); 52 for(int i=0;i<n;i++) 53 scanf("%d",&a[i]); 54 for(int i=0;i<n;i++) 55 scanf("%d",&b[i]); 56 FWT_xor(a,n,1);FWT_xor(b,n,1); 57 for(int i=0;i<n;i++) 58 { 59 b[i]=b[i]*powmod(a[i],mod-2)%mod; // b/a 60 } 61 FWT_xor(b,n,-1); //再逆变换 62 for(int i=0;i<n;i++) 63 printf("%d\n",b[i]); 64 }
原文：https://www.cnblogs.com/stranger-/p/9551392.html