写一段快速傅里叶变化求解多项式的代码
时间: 2023-06-27 09:02:53 浏览: 48
以下是用C++实现的快速傅里叶变换求解多项式的代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
struct Complex {
double real, imag;
Complex() { real = imag = 0; }
Complex(double x, double y) { real = x, imag = y; }
Complex operator+(const Complex &b) const { return Complex(real + b.real, imag + b.imag); }
Complex operator-(const Complex &b) const { return Complex(real - b.real, imag - b.imag); }
Complex operator*(const Complex &b) const { return Complex(real * b.real - imag * b.imag, real * b.imag + imag * b.real); }
} a[1 << 20], b[1 << 20];
void FFT(Complex *a, int n, int inv) {
for (int i = 0, j = 0; i < n; ++i) {
if (j > i) swap(a[i], a[j]);
int k = n;
while (j & (k >>= 1)) j &= ~k;
j |= k;
}
for (int i = 2; i <= n; i <<= 1) {
Complex wn(cos(2 * PI / i), inv * sin(2 * PI / i));
for (int j = 0; j < n; j += i) {
Complex w(1, 0);
for (int k = j; k < j + (i >> 1); ++k) {
Complex x = a[k], y = w * a[k + (i >> 1)];
a[k] = x + y, a[k + (i >> 1)] = x - y;
w = w * wn;
}
}
}
if (inv == -1) {
for (int i = 0; i < n; ++i) a[i].real /= n;
}
}
void conv(int len) {
FFT(a, len, 1), FFT(b, len, 1);
for (int i = 0; i < len; ++i) a[i] = a[i] * b[i];
FFT(a, len, -1);
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i <= n; ++i) scanf("%lf", &a[i].real);
for (int i = 0; i <= m; ++i) scanf("%lf", &b[i].real);
int len = 1;
while (len <= n + m) len <<= 1;
conv(len);
for (int i = 0; i <= n + m; ++i) printf("%d ", (int)(a[i].real + 0.5));
return 0;
}
```
其中,FFT函数用于进行快速傅里叶变换,conv函数用于实现多项式相乘。