社区讨论
求助!全部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 条回复,欢迎继续交流。
正在加载回复...