题目地址：洛谷：【P2553】[AHOI2001]多项式乘法 – 洛谷

题目描述

请编程序把含有乘法运算的代数多项式表达式改写成不含乘法的代数多项式。为简化计算，特做以下约定：
(1) 代数多项式表达式中只涉及一个代数符号 a ；
(2) 含有乘法运算的代数多项式表达式都是两个不含乘法运算的代数多项式直接相乘的形式，而且这两个参加乘法的代数多项式都用圆括号括起来了。乘法用符号表示，不得省略。
(3) 常数项以外的各项都是 xa^ y 的形式，其中 x 为该项的系数，而 y 是该项的指数。 x = 1时，不得简写成 a^ y ，应写成1a^ y 。
而 y = 1时，不得简写成 xa ，应写成 xa^1。

输入输出格式

输入格式：
文件中每行存放一个含有乘法的代数多项式表达式。

输出格式：
每行输出一个问题的解。要求指数大的项不能出现在指数小的项之后，指数相同的项必须合并同类项。不允许出现不必要的空白字符。

输入输出样例

输入样例#1：

(5a^2+3a^1+2)*(4a^1+1)
(5a^1+1)* (5a^1+1)

输出样例#1：

20a^3+17a^2+11a^1+2
25a^2+10a^1+1

题解

多项式处理出来裸的FFT。处理多项式的方法见代码。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cmath>
#include <cstring>

#include <algorithm>
#include <string>
#include <iostream>

const int MAXN = 1 << 21;
const double PI = acos(-1);

struct Complex {
    double real, imag;
    Complex(double real = 0, double imag = 0) : real(real), imag(imag) {}
    inline Complex operator+(const Complex &rhs) const {
        return Complex(real + rhs.real, imag + rhs.imag);
    }
    inline Complex operator-(const Complex &rhs) const {
        return Complex(real - rhs.real, imag - rhs.imag);
    }
    inline Complex operator*(const Complex &rhs) const {
        return Complex(real * rhs.real - imag * rhs.imag, real * rhs.imag + imag * rhs.real);
    }
    inline Complex& operator*=(const Complex &rhs) {
        Complex old = *this;
        real = old.real * rhs.real - old.imag * rhs.imag;
        imag = old.real * rhs.imag + old.imag * rhs.real;
        return *this;
    }
};

int rev[MAXN];
Complex a[MAXN], b[MAXN];

inline void fft(Complex *arr, int f, int n) {
    for(int i = 0; i < n; i++) {
        if(i < rev[i]) std::swap(arr[i], arr[rev[i]]);
    }
    for(int i = 1; i < n; i <<= 1) {
        Complex wn(cos(PI / i), f * sin(PI / i));
        for(int j = 0; j < n; j += i << 1) {
            Complex w(1, 0);
            for(int k = 0; k < i; k++) {
                Complex x = arr[j + k], y = w * arr[j + k + i];
                arr[j + k] = x + y;
                arr[j + k + i] = x - y;
                w *= wn;
            }
        }
    }
}

std::string str;
char str1[100005];

inline int parse(std::string str, Complex *arr) {
    int l = 1, r = 1, n = 0;
    for(;;) {
        r = str.find('+', l);
        if(r == std::string::npos) break;
        int a, k;
        sscanf(str.substr(l, r).c_str(), "%da^%d", &a, &k);
        arr[k].real = a;
        n++;
        l = ++r;
    }
    int a;
    sscanf(str.substr(l, str.length() - 1).c_str(), "%d", &a);
    arr[0].real = a;
    return n;
}

int main() {
    while(gets(str1)) {
        str = std::string(str1);
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        int ppos = str.find('*');
        if(ppos == std::string::npos) continue; // 不加这行会RE QAQ 
        int n = parse(str.substr(0, ppos), a), 
            m = parse(str.substr(ppos + 1, str.length() - 1), b), len = 0;
        m += n;
        for(n = 1; n <= m; n <<= 1) len++;
        for(int i = 0; i < n; i++) {
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
        }
        fft(a, 1, n);
        fft(b, 1, n);
        for(int i = 0; i <= n; i++) {
            a[i] *= b[i];
        }
        fft(a, -1, n);
        for(int i = m; i > 0; i--) {
            printf("%da^%d+", int(a[i].real / n + 0.5), i);
        }
        printf("%d\n", int(a[0].real / n + 0.5));
    }
    return 0;
}