oj.uz

답안 #66499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66499 2018-08-11T03:29:26 Z IOrtroiii Multiply (CEOI17_mul) C++14
100 / 100
 70 ms 9168 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 17;
const double PI = acos(-1);
typedef complex<double> base;

int n;
int rev[N];

void calc_rev(int n,int logn) {
	for (int i = 0; i < n; ++i) {
		rev[i] = 0;
		for (int j = 0; j < logn; ++j) if ((i >> j) & 1) {
			rev[i] |= (1 << (logn - 1 - j));
		}
	}
}

void fft(base a[], int n, bool invert) {
	for (int i = 0; i < n; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);
	
	for (int len = 2; len <= n; len <<= 1) {
		double alpha = 2 * PI / len * (invert ? -1 : 1);
		base wl = base(cos(alpha), sin(alpha));
		for (int i = 0; i < n; i += len) {
			base w = base(1);
			for (int j = 0; j < (len >> 1); ++j) {
				base u = a[i + j], v = a[i + j + (len >> 1)] * w;
				a[i + j] = u + v;
				a[i + j + (len >> 1)] = u - v;
				w *= wl;
			}
		}
	}
	
	if (invert) {
		for (int i = 0; i < n; ++i) a[i] /= n;
	}
}

vector<int> mult(vector<int> a, vector<int> b) {
	static base fa[N], fb[N], fc[N];
	int na = a.size(), nb = b.size();
	int n = 1, logn = 0;
	while (n < max(na, nb)) n <<= 1, logn++;
	n <<= 1, logn++;
	calc_rev(n, logn);
	for (int i = 0; i < n; ++i) fa[i] = fb[i] = base(0);
	for (int i = 0; i < na; ++i) fa[i] = base(a[i]);
	for (int i = 0; i < nb; ++i) fb[i] = base(b[i]);
	
	fft(fa, n, 0), fft(fb, n, 0);
	for (int i = 0; i < n; ++i) fc[i] = fa[i] * fb[i];
	fft(fc, n, 1);
	vector<int> ret;
	for (int i = 0; i < na + nb - 1; ++i) ret.push_back((int)(fc[i].real() + 0.5));
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	int n, m; string s, t;
	cin >> n >> m >> s >> t;
	vector<int> a, b;
	for (char c : s) a.push_back(c - '0');
	for (char c : t) b.push_back(c - '0');
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	// for (int x : a) cout << x << ' '; cout << '\n';
	// for (int x : b) cout << x << ' '; cout << '\n';
	vector<int> c = mult(a, b);
	c.push_back(0);
	// for (int x : c) cout << x << ' '; cout << '\n';
	for (int i = 0; i < c.size() - 1; ++i) {
		c[i + 1] += c[i] / 10;
		c[i] %= 10;
	}
	while (c.size() > 1 && !c.back()) c.pop_back();
	reverse(c.begin(), c.end());
	for (int x : c) cout << x;
}

Compilation message

mul.cpp: In function 'int main()':
mul.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < c.size() - 1; ++i) {
                  ~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 3 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 3 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 3 ms 552 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 3 ms 708 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 2 ms 708 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 3 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 3 ms 552 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 3 ms 708 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 2 ms 708 KB Output is correct
11 Correct 9 ms 1724 KB Output is correct
12 Correct 10 ms 1732 KB Output is correct
13 Correct 6 ms 1732 KB Output is correct
14 Correct 10 ms 1924 KB Output is correct
15 Correct 5 ms 1924 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 3 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 3 ms 552 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 3 ms 708 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 2 ms 708 KB Output is correct
11 Correct 9 ms 1724 KB Output is correct
12 Correct 10 ms 1732 KB Output is correct
13 Correct 6 ms 1732 KB Output is correct
14 Correct 10 ms 1924 KB Output is correct
15 Correct 5 ms 1924 KB Output is correct
16 Correct 31 ms 5068 KB Output is correct
17 Correct 57 ms 9040 KB Output is correct
18 Correct 62 ms 9040 KB Output is correct
19 Correct 70 ms 9168 KB Output is correct
20 Correct 60 ms 9168 KB Output is correct