[洛谷 3803]【模板】多项式乘法（FFT）

• 2018-02-14
• 0
• 0

Problem:

题目背景

这是一道FFT模板题

注意：虽然本题开到3s，但是建议程序在1s内可以跑完，本题需要一定程度的常数优化。

题目描述

给定一个n次多项式F(x)，和一个m次多项式G(x)。

请求出F(x)和G(x)的卷积。

输入输出格式

输入格式：

第一行2个正整数n,m。

接下来一行n+1个数字，从低到高表示F(x)的系数。

接下来一行m+1个数字，从低到高表示G(x)的系数。

输出格式：

一行n+m+1个数字，从低到高表示F(x)∗G(x)的系数。

输入输出样例

1 2
1 2
1 2 1

1 4 5 2

说明

保证输入中的系数大于等于 0 且小于等于9。

对于100%的数据：n, m ≤ 10⁶。

数据有一定梯度。

Solution:

FFT 模板题。

算法解释详见【转载】FFT 学习笔记，在此不详细赘述。

注意空间需要开到 2^⌈logn⌉ = 2097152。

据说 2016 年国家集训队毛爷爷的论文里提到 wys 的一种卡常方法，可以快一倍。

不加这个优化的 FFT 似乎并不能卡进 1s 内。。

Code: O(klogk), 其中k=max{n,m} [98667K, 1824MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const double PI = acos(-1.0);

inline int getint(){
	char ch; int num;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
	return num;
}

struct Complex{
	double r, i;
	
	Complex(): r(0), i(0) {}
	Complex(double r, double i): r(r), i(i) {}
	
	inline Complex operator + (const Complex &c) const {return Complex(r + c.r, i + c.i);}
	inline Complex operator - (const Complex &c) const {return Complex(r - c.r, i - c.i);}
	inline Complex operator * (const Complex &c) const {return Complex(r * c.r - i * c.i, r * c.i + i * c.r);}
};

int n, m, k;
Complex a[2100000], b[2100000], omega[2100000];

inline void FFT(Complex a[], int f){
	for(register int i = 0, j = 0; i < k; i++){
		if(i > j) swap(a[i], a[j]);
		for(register int l = k >> 1; (j ^= l) < l; l >>= 1);
	}  // 二进制序号反转 
	for(register int i = 1; i < k; i <<= 1){  // 半平面被分成的部分数 
		omega[0] = Complex(1, 0), omega[1] = Complex(cos(PI / i), f * sin(PI / i));
		for(register int j = 2; j < i; j++) omega[j] = omega[j - 1] * omega[1];
		for(register int j = 0; j < k; j += i << 1){  // 枚举每一组 
			Complex *wl = a + j, *wr = wl + i;
			for(register int k = 0; k < i; k++){
				Complex t = omega[k] * wr[k];
				wr[k] = wl[k] - t;
				wl[k] = wl[k] + t;
			}
		}
	}
	if(f == -1) for(register int i = 0; i < k; i++) a[i].r /= k;
}

int main(){
	n = getint(), m = getint();
	for(register int i = 0; i <= n; i++) a[i].r = getint();
	for(register int i = 0; i <= m; i++) b[i].r = getint();
	n += m;
	for(k = 1; k <= n; k <<= 1);
	FFT(a, 1), FFT(b, 1);
	for(register int i = 0; i < k; i++) a[i] = a[i] * b[i];
	FFT(a, -1);
	for(register int i = 0; i < n; i++) printf("%d ", int(a[i].r + 0.5));
	printf("%d\n", int(a[n].r + 0.5));
	return 0;
}