捞捞 - 66pts FFT求调
查看原帖
捞捞 - 66pts FFT求调
206814
封禁用户楼主2023/2/2 20:33

经过我不懈的努力,我成功干到了66pts.

#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, IDFT), yo = FFT(odd, n / 2, IDFT), 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)}, o = {1, 0};
    for(int i = 0; i < n / 2; i++, o = o * omega){
        result[i] = ye[i] + o * yo[i];
        result[i + n / 2] = ye[i] - o * 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 + 1)));
    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 20:33
加载中...