[洛谷 3803]【模板】多项式乘法(FFT)
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:
1 2 1 2 1 2 1
输出样例#1:
1 4 5 2
说明
保证输入中的系数大于等于 0 且小于等于9。
对于100%的数据:n, m ≤ 106。
数据有一定梯度。
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; }
发表评论