【题目链接】 点击打开链接

【题意】告诉两个多项式的系数，求多项式乘法后，每个的系数，多项式长度<=1e5。

【解题方法】 FFT模板题。

【AC代码】

//
//Created by BLUEBUFF 2016/1/9
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 4e5 + 10;
const int maxm = 300;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const double PI = acos(-1);
//head

typedef complex <double> Complex;

void rader(Complex *y, int len) {
    for(int i = 1, j = len / 2; i < len - 1; i++) {
        if(i < j) swap(y[i], y[j]);
        int k = len / 2;
        while(j >= k) {j -= k; k /= 2;}
        if(j < k) j += k;
    }
}
void fft(Complex *y, int len, int op) {
    rader(y, len);
    for(int h = 2; h <= len; h <<= 1) {
        double ang = op * 2 * PI / h;
        Complex wn(cos(ang), sin(ang));
        for(int j = 0; j < len; j += h) {
            Complex w(1, 0);
            for(int k = j; k < j + h / 2; k++) {
                Complex u = y[k];
                Complex t = w * y[k + h / 2];
                y[k] = u + t;
                y[k + h / 2] = u - t;
                w = w * wn;
            }
        }
    }
    if(op == -1) for(int i = 0; i < len; i++) y[i] /= len;
}

int num1[maxn], num2[maxn], sum[maxn];
Complex x1[maxn], x2[maxn];
int n, m, len1, len2;

int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        len1 = n + 1, len2 = m + 1;
        for(int i = 0; i < len1; i++) scanf("%d", &num1[i]);
        for(int i = 0; i < len2; i++) scanf("%d", &num2[i]);
        int len = 1;
        while(len < len1 * 2 || len < len2 * 2) len <<= 1;
        for(int i = 0; i < len1; i++) x1[i] = Complex(num1[i], 0);
        for(int i = len1; i < len; i++) x1[i] = Complex(0, 0);
        for(int i = 0; i < len2; i++) x2[i] = Complex(num2[i], 0);
        for(int i = len2; i < len; i++) x2[i] = Complex(0 ,0);
        fft(x1, len, 1);
        fft(x2, len, 1);
        for(int i = 0; i < len; i++) x1[i] = x1[i] * x2[i];
        fft(x1, len, -1);
        for(int i = 0; i < len; i++) sum[i] = (int)(x1[i].real() + 0.5);
        len = n + m;
        for(int i = 0; i < len; i++) printf("%d ", sum[i]);
        printf("%d\n", sum[len]);
    }
    return 0;
}