社区讨论

求助!全部RE 玄关一枚

P1919【模板】高精度乘法 / A*B Problem 升级版参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi8wjksr
此快照首次捕获于
2025/11/21 21:34
3 个月前
此快照最后确认于
2025/11/21 22:30
3 个月前
查看原帖
玄关一枚
写的是 FFT,但是全部 RE。
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 20000005;
const double PI = acos(-1.0);
struct comp {
	double a, b;  // a+b*i
	inline comp(double x = 0, double y = 0) {
		a = x;
		b = y;
	}
	inline comp operator + (comp x) {
		return comp(a + x.a, b + x.b);
	}
	inline comp operator - (comp x) {
		return comp(a - x.a, b - x.b);
	}
	inline comp operator * (comp x) {
		return comp(a * x.a - b * x.b, a * x.b + b * x.a);
	}
}a[N], b[N];
int n, m, lim = 1, l, r[N];
inline void FFT(comp * x, int k) {
	for (int i = 0; i < lim; i++) {
		if (i < r[i]) {
			swap(x[i], x[r[i]]);
		}
	}
	for (int mid = 1; mid < lim; mid *= 2) {
		comp w_n(cos(PI / mid), k * sin(PI / mid));
		int len = mid * 2;
		for (int j = 0; j < lim; j += len) {
			comp w(1, 0);
			for (int k = 0; k < mid; k++, w = w * w_n) {
				comp t = x[j + k], y = w * x[j + mid + k];
				x[j + k] = t + y;
				x[j + mid + k] = t - y; 
			}
		}
	}
}
int out[N];
int main() {
	string A, B; 
	cin >> A >> B;
	n = A.size() - 1;
	m = B.size() - 1;
	for (int i = 0; i <= n; i++) {
		a[i].a = A[n - i] - '0';
	}
	for (int i = 0; i <= m; i++) {
		b[i].a = B[m - i] - '0';
	}
	while (lim <= n + m) {
		lim *= 2;
		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);
	
	for (int i = 0; i <= n + m; i++) {
		out[i] += (int)(a[i].a / lim + 0.5);
		out[i + 1] = out[i] / 10;
		out[i] %= 10;
	}
	for (int i = n + m + 1; i >= 0; i--) {
		if(out[i] || !i) {
			cout << out[i];
		}
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...