[SOJ #47]集合并卷积

题目大意：给你两个多项式$A,B$，求多项式$C$使得：
$$
C_n=\sum\limits_{x|y=n}A_xB_y
$$
题解：$FWT$，他可以解决形如$C_n=\sum\limits_{x\oplus y=n}A_xB_y$的问题，其中$\oplus$为位运算（一般为$or,and,xor$）

or：

void FWT(int *A) {

	for (int mid = 1; mid < lim; mid <<= 1)

		for (int i = 0; i < lim; i += mid << 1)

			for (int j = 0; j < mid; ++j) A[i + j + mid] += A[i + j];

}

void IFWT(int *A) {

	for (int mid = 1; mid < lim; mid <<= 1)

		for (int i = 0; i < lim; i += mid << 1)

			for (int j = 0; j < mid; ++j) A[i + j + mid] -= A[i + j];

}

and：

void FWT(int *A) {

	for (int mid = 1; mid < lim; mid <<= 1)

		for (int i = 0; i < lim; i += mid << 1)

			for (int j = 0; j < mid; ++j) {

				int X = A[i + j], Y = A[i + j + mid];

				A[i + j] = X + Y, A[i + j + mid] = X - Y;

			}

}

void IFWT(int *A) {

	for (int mid = 1; mid < lim; mid <<= 1)

		for (int i = 0; i < lim; i += mid << 1)

			for (int j = 0; j < mid; ++j) {

				int X = A[i + j], Y = A[i + j + mid];

				A[i + j] = X + Y, A[i + j + mid] = X - Y;

			}

	for (int i = 0; i < lim; ++i) A[i] /= lim;

}

xor：

void FWT(int *A) {

	for (int mid = 1; mid < lim; mid <<= 1)

		for (int i = 0; i < lim; i += mid << 1)

			for (int j = 0; j < mid; ++j) {

				int X = A[i + j], Y = A[i + j + mid];

				A[i + j] = X + Y, A[i + j + mid] = X - Y;

			}

}

void IFWT(int *A) {

	for (int mid = 1; mid < lim; mid <<= 1)

		for (int i = 0; i < lim; i += mid << 1)

			for (int j = 0; j < mid; ++j) {

				int X = A[i + j], Y = A[i + j + mid];

				A[i + j] = X + Y, A[i + j + mid] = X - Y;

			}

	for (int i = 0; i < lim; ++i) A[i] /= lim;

}

卡点：无

C++ Code：

#include <cstdio>

#include <cctype>

inline int read() {

	static int ch;

	while (isspace(ch = getchar())) ;

	return ch & 15;

}

#define N 1048576

int lim;

inline void init(const int n) {

	lim = 1; while (lim < n) lim <<= 1;

}

inline void FWT(long long *A) {

	for (int mid = 1; mid < lim; mid <<= 1)

		for (int i = 0; i < lim; i += mid << 1)

			for (int j = 0; j < mid; ++j) A[i + j + mid] += A[i + j];

}

inline void IFWT(long long *A) {

	for (int mid = 1; mid < lim; mid <<= 1)

		for (int i = 0; i < lim; i += mid << 1)

			for (int j = 0; j < mid; ++j) A[i + j + mid] -= A[i + j];

}

int n;

long long A[N], B[N];

int main() {

	scanf("%d", &n);

	for (int i = 0; i < n; ++i) A[i] = read();

	for (int i = 0; i < n; ++i) B[i] = read();

	init(n);

	FWT(A), FWT(B);

	for (int i = 0; i < lim; ++i) A[i] *= B[i];

	IFWT(A);

	for (int i = 0; i < n; ++i) {

		printf("%lld", A[i]);

		putchar(i == (n - 1) ? '\n' : ' ');

	}

	return 0;

}

巴特西

[SOJ #47]集合并卷积

最新文章

热门文章