提交记录 3292


用户 题目 状态 得分 用时 内存 语言 代码长度
chrogeek 1004. 【模板题】高精度乘法 Accepted 100 1.605 s 93312 KB C++ 1.73 KB
提交时间 评测时间
2018-07-11 21:41:08 2020-07-31 21:15:06
#include <vector>
#include <complex>
#include <cstring>
#include <algorithm>
using namespace std;
#define complex complex<double>
#define polynomial vector<complex>
const int maxn = 2100005;
const double PI = acos(-1.0);
char A[maxn], B[maxn];
int a[maxn], b[maxn], c[maxn], n, m;
polynomial va, vb;
int rev[maxn];
void DFT(polynomial &a, bool inv) {
	int n = a.size();
	for (int i = 0; i < n; ++i) if (rev[i] < i) swap(a[i], a[rev[i]]);
	double pi = inv ? -PI : PI;
	for (int step = 1; step < n; step <<= 1) {
		double theta = pi / step;
		for (int k = 0; k < step; ++k) {
			complex omega_k = exp(complex(0, theta * k));
			for (int ek = k; ek < n; ek += step << 1) {
				int ok = ek + step;
				complex t = a[ok] * omega_k;
				a[ok] = a[ek] - t;
				a[ek] += t;
			}
		}
	}
	if (inv) for (int i = 0; i < n; ++i) a[i] /= n;
}
int poly_multiply(int *a, int n, int *b, int m, int *c) {
	int t, bit;
	for (t = 2, bit = 1; t < n + m + 2; t <<= 1, ++bit);
	rev[0] = 0;
	for (int i = 1; i < t; ++i) {
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
	}
	va.resize(t, 0);
	vb.resize(t, 0);
	for (int i = 0; i <= n; ++i) va[i] = a[i];
	for (int i = 0; i <= m; ++i) vb[i] = b[i];
	DFT(va, false);
	DFT(vb, false);
	for (int i = 0; i < t; ++i) va[i] *= vb[i];
	DFT(va, true);
	for (int i = 0; i <= n + m; ++i) c[i] = int(va[i].real() + 0.5);
	for (int i = 0; i <= n + m; ++i) c[i + 1] += c[i] / 10, c[i] %= 10;
	return n + m + int(bool(c[n + m + 1]));
}
int main() {
	scanf("%s%s", A, B);
	n = strlen(A), m = strlen(B);
	for (int i = 0; i < n; ++i) a[i] = A[n - 1 - i] - '0';
	for (int i = 0; i < m; ++i) b[i] = B[m - 1 - i] - '0';
	int x = poly_multiply(a, n, b, m, c);
	while (c[x] == 0 && x) --x;
	for (int i = x; ~i; --i) putchar('0' + c[i]);
	putchar('\n');
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #11.605 s91 MB + 128 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-04-18 21:16:37 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠