牛客网暑期ACM多校训练营（第九场）A （Circulant Matrix）

本文主要是介绍牛客网暑期ACM多校训练营（第九场）A （Circulant Matrix），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
Niuniu has recently learned how to use Gaussian elimination to solve systems of linear equations.
Given n and a[i], where n is a power of 2, let's consider an n x n matrix A.

The index of A[i][j] and a[i] are numbered from 0.
The element A[i][j] satisfies A[i][j] = a[i xor j],
https://en.wikipedia.org/wiki/Bitwise_operation#XOR

Let p = 1000000007.
Consider the equation
A x = b (mod p)
where A is an n x n matrix, and x and b are both n x 1 row vector.

Given n, a[i], b[i], you need to solve the x.
For example, when n = 4, the equations look like
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)
and the matrix A can be decided by the array a.

It is guaranteed that there is a unique solution x for these equations.
输入描述:
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
输出

4
3
2
1

题意：给出两数组，a,b，问按照题意生成A[i][j]=a[i^j]，然后解方程组x。

思路：其实看到异或就应该隐隐约约感觉到FWT有关，观察一下发现i^j^j=i。那么

这个就很显然了，套上FWT做就行了。顺便粘一下官方题解。

代码：

const ll mod=1e9+7;
ll N,inv2;
ll a[1000005],b[1000005];
long long qpow(long long a,long long b)
{
a=a%mod;
long long ans=1;
while(b)
{
if(b&1)
{
ans=(ans*a)%mod;
b--;
}
b>>=1;
a=a*a%mod;
}
return ans;
}
void FWT(ll *a,int opt)
{
inv2=qpow(2,mod-2);
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 main()
{
scanf("%lld",&N);
for(int i=0;i<N;i++) scanf("%lld",&a[i]);
for(int i=0;i<N;i++) scanf("%lld",&b[i]);
FWT(a,1);
FWT(b,1);
for(int i=0;i<N;i++) a[i]=(b[i]*qpow(a[i],mod-2))%mod;
FWT(a,-1);
for(int i=0;i<N;i++)
{
cout<<a[i]<<endl;
}
}