牛客网多校赛第九场A-circulant matrix【数论】

时间:2023-03-10 03:11:28
牛客网多校赛第九场A-circulant matrix【数论】

链接:https://www.nowcoder.com/acm/contest/147/A

来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒

空间限制:C/C++ 262144K,其他语言524288K

64bit IO Format: %lld

题目描述

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.

示例1

输入

复制

4
1 10 100 1000
1234 2143 3412 4321

输出

复制

4
3
2
1

看了一整天也没有真的搞明白FWT和FFT到底是干吗玩意儿 最后绝望的我决定退而求其次

大概知道一下怎么用的就行了

简而言之 FFT就是用来算多项式乘法(卷积),FWT就是用来算位运算卷积

牛客网多校赛第九场A-circulant matrix【数论】

FFT算法,是用于优化卷积,而FWT是用于优化逻辑运算卷积。形如下图:

牛客网多校赛第九场A-circulant matrix【数论】

它同样可以写作

牛客网多校赛第九场A-circulant matrix【数论】

因为 i ^ j ^ j = i 把这道题的等式列出来 就会发现

牛客网多校赛第九场A-circulant matrix【数论】

FWT(B) = FWT(A) * FWT(X)

所以对b 和 a 求一次FWT

然后对b / a做FWT的逆变换IFWT


#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#define inf 1e18
using namespace std;
int n;
const long long p = 1e9 + 7;
const int maxn = 263000;
long long a[maxn], b[maxn]; long long qpow(long long a, long long b)
{
long long ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % p;
}
a = a * a % p;
b = b >> 1;
}
return ans;
} void fwt(long long a[])
{
for (int d = 1; d < n; d <<= 1) {
for (int m = d << 1, i = 0; i < n; i += m) {
for (int j = 0; j < d; j++) {
long long x = a[i + j], y = a[i + j + d];
a[i + j] = (x + y) % p;
a[i + j + d] = (x - y + p) % p;
}
}
}
} void ifwt(long long a[])
{
long long inv = qpow(2, p - 2);//并不知道为什么是p - 2
for (int d = 1; d < n; d <<= 1) {
for (int m = d << 1, i = 0; i < n; i += m) {
for (int j = 0; j < d; j++) {
long long x = a[i + j], y = a[i + j + d];
a[i + j] = (x + y) % p;
a[i + j + d] = (x - y + p) % p;
a[i + j] = a[i + j] * inv % p;
a[i + j + d] = a[i + j + d] * inv % p;
}
}
}
} int main()
{
while (scanf("%d", &n) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &b[i]);
} fwt(a);
fwt(b);
for (int i = 0; i < n; i++) {
a[i] = (b[i] * qpow(a[i], p - 2)) % p;
}
ifwt(a);
for (int i = 0; i < n; i++) {
cout << a[i] << endl;
}
}
}