oj.uz

답안 #526087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526087 2022-02-13T17:03:30 Z eric00513 씽크스몰 (kriii3_TT) C++17
30 / 30
 3153 ms 198052 KB 
#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using ll = long long;
using base = complex<long double>;

const long double PI = acos(-1.L);

void fft(vector<base>& a, bool inv) {
	int n = sz(a);
	for (int i = 1, j = 0; i < n; i++) {
		int bit = n >> 1;
		while (j >= bit) j -= bit, bit >>= 1;
		j += bit;
		if (i < j) swap(a[i], a[j]);
	}
	for (int len = 2; len <= n; len <<= 1) {
		vector<base> w(len >> 1);
		for (int i = 0; i < (len >> 1); i++) {
			long double ang = 2 * PI * i / len * (inv ? -1 : 1);
			w[i] = base(cos(ang), sin(ang));
		}
		for (int i = 0; i < n; i += len) {
			for (int j = 0; j < len / 2; j++) {
				base u = a[i + j], v = a[i + j + len / 2] * w[j];
				a[i + j] = u + v;
				a[i + j + len / 2] = u - v;
			}
		}
	}
	if (inv) for (int i = 0; i < n; i++) a[i] /= n;
}

vector<ll> multiply(vector<int>& a, vector<int>& b) {
	vector<base> fa(all(a)), fb(all(b));
	int n = 1;
	while (n < max(sz(a), sz(b))) n <<= 1;
	fa.resize(n), fb.resize(n);
	fft(fa, false); fft(fb, false);
	for (int i = 0; i < n; i++) fa[i] *= fb[i];
	fft(fa, true);
	vector<ll> ret(n);
	for (int i = 0; i < n; i++) ret[i] = (ll)(fa[i].real() + (fa[i].real() > 0 ? 0.5 : -0.5));
	return ret;
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int n, m;
	cin >> n >> m;
	n++, m++;
	int k = 1;
	while (k < 2 * max(n, m) - 1) k <<= 1;
	vector<int> a(k), b(k);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) cin >> b[i];

	vector<ll> res = multiply(a, b);
	ll ans = 0;
	for (int i = 0; i < n + m - 1; i++) ans ^= res[i];
	cout << ans << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 440 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 444 KB Output is correct
8 Correct 3 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 3140 KB Output is correct
2 Correct 347 ms 23200 KB Output is correct
3 Correct 360 ms 23300 KB Output is correct
4 Correct 352 ms 23208 KB Output is correct
5 Correct 360 ms 23324 KB Output is correct
6 Correct 349 ms 23224 KB Output is correct
7 Correct 361 ms 23292 KB Output is correct
8 Correct 352 ms 23160 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 771 ms 45592 KB Output is correct
2 Correct 1500 ms 91368 KB Output is correct
3 Correct 1522 ms 91604 KB Output is correct
4 Correct 3107 ms 197872 KB Output is correct
5 Correct 3082 ms 197920 KB Output is correct
6 Correct 3100 ms 197832 KB Output is correct
7 Correct 3122 ms 198052 KB Output is correct
8 Correct 3153 ms 197812 KB Output is correct