FFT66pts,WA on #7,8,9
查看原帖
FFT66pts,WA on #7,8,9
347839
Daniel_7216楼主2021/12/28 22:28

RT,找不出错,求各位大佬调试亿下


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int A[3000001], B[3000001];
int len1, len2, len, ans[6000001];
const long double PI = acos(-1.0);
struct a_bi{
	long double x, y;
	a_bi (long double x_ = 0.0, long double y_ = 0.0){
		x = x_;
		y = y_;
	}
	a_bi operator -(const a_bi &a) const{
		return a_bi(x - a.x, y - a.y);
	}
	a_bi operator +(const a_bi &a) const{
		return a_bi(x + a.x, y + a.y);
	}
	a_bi operator *(const a_bi &a) const{
		return a_bi(x * a.x - y * a.y, x * a.y + y * a.x);
	}
};
//令A(x)=a0+a1x+a2x^2+a3x^3+.....+a4x^4,如果令x=10,则这个多项式可以表示一个大整数。
//那么,现在只用知道新的多项式的系数即可。 
a_bi x1[1000001], x2[1000001];
void reverse(a_bi F[]){
	for (int i = 1, j = len / 2, k; i < len - 1; i++){
		if (i < j) swap(F[i], F[j]);
		k= len / 2;
		while (j >= k){
			j = j - k;
            k = k / 2;
		}
		if (j < k) j += k;
	}
} 
void fft(a_bi F[], int dft){
	reverse(F);
	for (int i = 2; i <= len; i *= 2){
		a_bi omega_n(cos(2 * PI / i), sin(dft * 2 * PI / i));
		for (int j = 0; j < len; j += i){
			a_bi w(1, 0);
			for (int k = j; k < j + i / 2; k++){
				a_bi X = F[k];
				a_bi Y = w * F[i / 2 + k];
				F[k] = X + Y;
				F[i / 2 + k] = X - Y;
				w = w * omega_n;
			}
		}
	}
    if (dft == -1){
        for (int i = 0; i < len; i++){
            F[i].x /= len;
        }
    }
}
int main(){
    scanf("%d%d", &len1, &len2);
    len1++;
    len2++;
    for (int i = 0; i < len1; i++){
        scanf("%d", &A[i]);
    }
    for (int i = 0; i < len2; i++){
        scanf("%d", &B[i]);
    }
	len = 2;
	for (int i = 1; (1 << i) < len1 + len2 - 1; i++) len *= 2;
	for (int i = 0; i < len1; i++){
		x1[i] = a_bi((long double)(A[len1 - 1 - i]), 0);
	}
	for (int i = 0; i < len2; i++){
		x2[i] = a_bi((long double)(B[len2 - 1 - i]), 0);
	}
	for (int i = len1; i < len; i++){
		x1[i] = a_bi(0, 0);
	}
	for (int i = len2; i < len; i++){
		x2[i] = a_bi(0, 0);
	}
	fft(x1, 1);
	fft(x2, 1);
	for (int i = 0; i < len; i++){
        x1[i] = x1[i] * x2[i];
    }
    fft(x1, -1);
	for (int i = 0; i < len; i++){
		ans[i] = (int)(x1[i].x + 0.5);
	}
    int i;
	for (i = len1 + len2 - 2; i >= 0; i--){
		printf("%d ", ans[i]);
	}
	return 0;
}
2021/12/28 22:28
加载中...