题目链接：https://www.nowcoder.com/acm/contest/147/A
题解来自（侵删）：
https://blog.csdn.net/dllpXFire/article/details/81748315http://tokitsukaze.live/2018/08/16/2018niuke9.A/题意：有p = 1000000007。考虑等式：A x = b (mod p)，这里A是一个 n x n 的矩阵，x 和 b 都是 n x 1 行向量。
给你一个a数组和b数组，构造出A[i][j]矩阵（A[i][j] = a[i xor j]），解x数组。
n等于4的时候有： A[0][0]*x[0] + A[0][1]*x[1] + A[0][2]*x[2] + A[0][3]*x[3] = b[0] (mod p) A[1][0]*x[0] + A[1][1]*x[1] + A[1][2]*x[2] + A[1][3]*x[3] = b[1] (mod p) A[2][0]*x[0] + A[2][1]*x[1] + A[2][2]*x[2] + A[2][3]*x[3] = b[2] (mod p) A[3][0]*x[0] + A[3][1]*x[1] + A[3][2]*x[2] + A[3][3]*x[3] = b[3] (mod p)
解析：
把上面随便拿出几行写出来，会发现是有：
a0*x0+a1*x1+a2*x2+a3*x3=b0
a1*x0+a0*x1+a3*x2+a2*x3=b1
a2*x0+a3*x1+a0*x2+a1*x3=b2
a3*x0+a2*x1+a1*x2+a0*x3=b3
然后会发现 a 数组下标 i 与相应位置上的 x 数组下标 j 的异或值就是这一行的 b 数组下标k。
FWT可以对于两个数组a和b，求出他们的位运算卷积c，使得：
本题中有：
然后观察原本的FWT的过程：对a，x数组做FWT，b[i]=a[i]*x[i]，然后对b数组做UFWT。
本题中我们可以：先对a，b数组做FWT，然后x[i]=b[i]/a[i]，即x[i]=b[i]*(a[i]的除法逆元)，最后对x数组做UFWT，就把x数组还原了。
代码(261ms)：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=262144+5; const int MOD =1e9+7; const int inv2=5e8+4; int n,N,a[MAXN],b[MAXN],x[MAXN]; int pow_mod(int n,int k) { int res=1; n=n%MOD; while(k>0) { if(k&1) res=(long long)res*n%MOD; n=(long long)n*n%MOD; k>>=1; } return res; } void FWT_xor(int *a,int opt) { 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) { int 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 inline read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void write(int x) { if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int main() { n=read(); N=n; for(int i=0;i<n;i++) a[i]=read(); for(int i=0;i<n;i++) b[i]=read(); FWT_xor(a,1); FWT_xor(b,1); for(int i=0;i<n;i++) x[i]=(long long)pow_mod(a[i],MOD-2)*b[i]%MOD; FWT_xor(x,-1); for(int i=0;i<n;i++) { write(x[i]); putchar(10); } return 0; }
