洛谷 - P3803 多项式乘法（FFT）

传送门：洛谷 - P3803

思路分析

模板

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (int)(x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int N = 4e6+10;


int n, m;
int limit = 1,mcnt,rev[N];
struct cp {
    double x, y;
    cp (double x = 0, double y = 0) : x(x), y(y) { }
    friend cp operator * (cp J, cp Q) {
        return cp(J.x * Q.x - J.y * Q.y, J.x * Q.y + J.y * Q.x);
    }
    friend cp operator - (cp J, cp Q) {
        return cp(J.x - Q.x, J.y - Q.y);
    }
    friend cp operator + (cp J, cp Q) {
        return cp(J.x + Q.x, J.y + Q.y);
    }

} a[N], b[N];

void FFT(cp * A, int type) {
    for(int i = 0; i < limit; ++ i)
        if(i < rev[i])
            swap(A[i], A[rev[i]]);
    for(int mid = 1; mid < limit; mid <<= 1) {
        cp wn(cos(PI / mid), type * sin(PI / mid));
        for(int len = mid << 1, pos = 0; pos < limit; pos += len) {
            cp w(1, 0);
            for(int k = 0; k < mid; ++ k, w = w * wn) {
                cp x = A[pos + k];
                cp y = w * A[pos + mid + k];
                A[pos + k] = x + y;
                A[pos + mid + k] = x - y;
            }
        }
    }
    if(type == 1) return ;
    for(int i = 0; i <= limit; ++ i)
        A[i].x /= limit;
}
signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    IOS;
    cin>>n>>m;
    for(int i = 0; i <= n; ++ i) cin>>a[i].x;
    for(int i = 0; i <= m; ++ i) cin>>b[i].x;
    while(limit <= n + m) limit <<= 1, mcnt ++ ;
    for(int i = 0; i < limit; ++ i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (mcnt - 1));
    FFT(a, 1);
    FFT(b, 1);
    for(int i = 0; i <= limit; ++ i) a[i] = a[i] * b[i];
    FFT(a, -1);
    for(int i = 0; i <= n + m; ++ i) printf("%d ", (int)(a[i].x + 0.5));
}