萌新学妹求助!!!
查看原帖
萌新学妹求助!!!
385145
神眷之樱花楼主2021/6/25 11:31

可以过下载数据,但是交上去全 RE。

#include<cstdio>
#include<iostream>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const double PI = acos(-1.0);
const int N = 4e6 + 10;

struct complex {
	double x, y;
	complex(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}
	complex operator + (complex b) {return complex(x + b.x, y + b.y);}
	complex operator - (complex b) {return complex(x - b.x, y - b.y);}
	complex operator * (complex b) {return complex(x * b.x - y * b.y, x * b.y + y * b.x);}
}a[N], b[N];

int num[N], n, m, l, r[N], lim = 1;

void FFT(complex *A, int type) {
	for(int i = 0; i < lim; i++)
		if(i < r[i]) swap(A[i], A[r[i]]);
	for(int mid = 1; mid < lim; mid <<= 1) {
		complex Wn(cos(PI / mid), type * sin(PI / mid));
		for(int R = mid << 1, j = 0; j < lim; j += R) {
			complex w(1, 0);
			for(int k = 0; k < mid; k++, w = w * Wn) {
				complex x = A[j + k], y = w * A[j + k + mid];
				A[j + k] = x + y;
				A[j + k + mid] = x - y;
			}
		}
	}
}

inline int read(complex *A, int &len) {
	int c = getchar(); len = -1;
	for(; !isdigit(c); c = getchar());
	
	for(; isdigit(c); c = getchar())
		num[++len] = c - '0';
	for(int i = 0; i <= len; i++)
		A[i].x = num[len - i];
}

int main() {
	read(a, n);
	read(b, m);
	while(lim <= n + m) lim <<= 1, ++l;
	for(int i = 0; i < lim; i++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	FFT(a, 1);
	FFT(b, 1);
	for(int i = 0; i <= lim; i++) a[i] = a[i] * b[i];
	FFT(a, -1);
	memset(num, 0, sizeof(num));
	for(int i = n + m; ~i; i--)
		num[i] = (int) (a[i].x / lim + 0.5);
	for(int i = 0; i <= n + m; i++)
		if(num[i] > 9) 
			num[i + 1] += num[i] / 10,
			num[i] %= 10;
	for(int i = n + m + (num[n + m + 1] > 0); ~i; i--)
		putchar(num[i] + '0');
	return 0;
}
2021/6/25 11:31
加载中...