求调FFT多项式乘法递归实现的
  • 板块学术版
  • 楼主Sukilin
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/18 18:48
  • 上次更新2025/1/18 21:33:46
查看原帖
求调FFT多项式乘法递归实现的
959201
Sukilin楼主2025/1/18 18:48
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <complex>
const int N = 1e6 + 7;
const long double pi = 3.14159265358979323846;
std::vector <std::complex<long double>> FFT(std::vector <std::complex<long double>> a, int n, int o) {
	if(n == 1) return a;
    std::complex <long double> Wn = {std::cos(2 * pi / n), o * std::sin(2 * pi / n)};
    std::complex <long double> w = 1;
    std::vector <std::complex <long double>> a0(n >> 1), a1(n >> 1);
    for(int i = 0; i < (n >> 1); i++)
        a0[i] = a[i << 1], a1[i] = a[(i << 1) | 1];
    std::vector <std::complex<long double>> y0 = FFT(a0, n >> 1, o);
    std::vector <std::complex<long double>> y1 = FFT(a1, n >> 1, o);
    std::vector <std::complex<long double>> y(n);
    for(int i = 0; i < (n >> 1); i++, w = w * Wn) {
        y[i] = y0[i] + y1[i] * w;
        y[i + (n >> 1)] = y0[i] - y1[i] * w;
    }
    return y;
}
int n, m;
int main() {
    std::cin >> n >> m;
    int l = 1;
    while(l <= m + n) l <<= 1;
    std::vector <std::complex<long double>> a(l), b(l);
    for(int i = 0; i <= n; i++) {
    	int t; 
    	std::cin >> t;
    	a[i] = t;
    }
    for(int i = 0; i <= m; i++) {
    	int t;
    	std::cin >> t;
    	b[i] = t;
    }
    std::vector <std::complex<long double>> fa = FFT(a, l, 1);
    std::vector <std::complex<long double>> fb = FFT(b, l, 1);
    for(int i = 0; i <= l; i++) a[i] = fa[i] * fb[i];
    a = FFT(a, l, -1);
    for(int i = 0; i <= n + m; i++) std::cout << (int)(a[i].real() / l + 0.5) << ' ';
    std::cout << '\n';
    return 0;
}
2025/1/18 18:48
加载中...