牛客网多校赛第九场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

输出

复制

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

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

简而言之 FFT就是用来算多项式乘法（卷积），FWT就是用来算位运算卷积

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

它同样可以写作

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

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;
		}
	}
}