Submission #66499

#	Time	Username	Problem	Language	Result	Execution time	Memory
66499		IOrtroiii	Multiply (CEOI17_mul)	C++14	100 / 100	70 ms	9168 KiB

mul

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30