oj.uz

답안 #15062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15062 2015-07-11T08:03:04 Z hongjun7 씽크스몰 (kriii3_TT) C++
20 / 30
 305 ms 25476 KB 
#include <cstdio>
#define _USE_MATH_DEFINES
#include <math.h>
#include <complex>
#include <vector>
#include <algorithm>
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
typedef complex<double> base;
typedef long long ll;
void fft(vector <base> &a, bool invert) {
	int n = sz(a);
	for (int i = 1, j = 0; i<n; i++) {
		int bit = n >> 1;
		for (; j >= bit; bit >>= 1) j -= bit;
		j += bit;
		if (i < j) swap(a[i], a[j]);
	}
	for (int len = 2; len <= n; len <<= 1) {
		double ang = 2 * M_PI / len*(invert ? -1 : 1);
		base wlen(cos(ang), sin(ang));
		for (int i = 0; i<n; i += len) {
			base w(1);
			for (int j = 0; j<len / 2; j++) {
				base u = a[i + j], v = a[i + j + len / 2] * w;
				a[i + j] = u + v;
				a[i + j + len / 2] = u - v;
				w *= wlen;
			}
		}
	}
	if (invert) {
		for (int i = 0; i<n; i++) a[i] /= n;
	}
}
void multiply(const vector<ll> &a, const vector<ll> &b, vector<ll> &res) {
	vector <base> fa(all(a)), fb(all(b));
	int n = 1;
	while (n < 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);
	res.resize(n);
	for (int i = 0; i < n; i++) res[i] = (ll)(fa[i].real() + (fa[i].real()>0 ? 0.5 : -0.5));
	ll r = res[0];
	for (int i = 1; i < n; i++)
		r ^= res[i];
	printf("%lld", r);
}
int n, m, x;
int main() {
	scanf("%d%d", &n, &m);
	vector <ll> a(n + 1), b(m + 1), res;
	for (int i = 0; i <= n; i++) scanf("%lld", &a[i]);
	for (int i = 0; i <= m; i++) scanf("%lld", &b[i]);
	if (n < m) for (int i = n; i <= m; i++) a.push_back(0);
	else for (int i = m; i <= n; i++) b.push_back(0);
	multiply(a, b, res);
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1680 KB Output is correct
2 Correct 0 ms 1680 KB Output is correct
3 Correct 0 ms 1680 KB Output is correct
4 Correct 0 ms 1680 KB Output is correct
5 Correct 0 ms 1680 KB Output is correct
6 Correct 0 ms 1680 KB Output is correct
7 Correct 0 ms 1680 KB Output is correct
8 Correct 0 ms 1680 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3264 KB Output is correct
2 Correct 132 ms 13400 KB Output is correct
3 Correct 130 ms 13696 KB Output is correct
4 Correct 144 ms 13928 KB Output is correct
5 Correct 140 ms 14156 KB Output is correct
6 Correct 141 ms 14024 KB Output is correct
7 Correct 133 ms 14280 KB Output is correct
8 Correct 133 ms 14280 KB Output is correct

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 305 ms 25476 KB Output isn't correct
2 Halted 0 ms 0 KB -