捞 - FFT过不去了
查看原帖
捞 - FFT过不去了
206814
封禁用户楼主2023/2/2 18:22

样例过了,求调

#include <bits/stdc++.h>
using namespace std;
struct Complex{
    long double Real = 0;
    long double Virtual = 0;
    friend Complex operator+(Complex a, Complex b){
        return {a.Real + b.Real, a.Virtual + b.Virtual};
    }
    friend Complex operator-(Complex a, Complex b){
        return a + Complex{-b.Real, -b.Virtual};
    }
    friend Complex operator*(Complex a, Complex b){
        return {a.Real * b.Real - a.Virtual * b.Virtual, a.Virtual * b.Real + a.Real * b.Virtual};
    }
};
vector<Complex> FFT(vector<Complex>& ratios, int n, bool IDFT = false){
    if(ratios.size() == 1) return vector<Complex>(n, ratios[0]); 
    vector<Complex> even, odd;
    for(int i = 0; i < ratios.size(); i++){
        if(i % 2 == 0) even.push_back(ratios[i]);
        else odd.push_back(ratios[i]);
    }
    vector<Complex> ye = FFT(even, n / 2), yo = FFT(odd, n / 2), result;
    result.resize(n);
    int flag = (IDFT) ? -1 : 1;
    Complex omega = {cos(2 * M_PI / (long double)n), flag * sin(2 * M_PI / (long double)n)};
    result[0] = ye[0] + yo[0];
    result[n / 2] = ye[0] - yo[0];
    for(int i = 1; i < n / 2; i++, omega = omega * omega){
        result[i] = ye[i] + omega * yo[i];
        result[i + n / 2] = ye[i] - omega * yo[i];
    }
    return result;
}
vector<Complex> F, G;
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0, t; i <= n; i++){
        scanf("%d", &t);
        F.push_back(Complex{(long double)t, 0.0});
    }
    for(int i = 0, t; i <= m; i++){
        scanf("%d", &t);
        G.push_back(Complex{(long double)t, 0.0});
    }
    int len = (1 << (int)ceil(log2(n + m)));
    vector<Complex> A = FFT(F, len), B = FFT(G, len), C;
    for(int i = 0; i < len; i++){
        C.push_back(A[i] * B[i]);
    }
    vector<Complex> Answer = FFT(C, len, true);
    for(int i = 0; i <= n + m; i++){
        printf("%.0Lf ", round(Answer[i].Real / (long double)len));
    }
    putchar('\n');
    return 0;
}
2023/2/2 18:22
加载中...