oj.uz

답안 #32093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
32093 2017-09-25T01:31:11 Z h0ngjun7 씽크스몰 (kriii3_TT) C++14
30 / 30
 3553 ms 280624 KB 
#include <stdio.h>
#include <complex>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

typedef long long ll;
const double PI = 3.1415926535897932384626433832795;

namespace FFT {
	typedef complex<double> base;
	void FFT(vector <base> &v, bool inv) {
		vector<base> w(v.size());
		for (int i = 0; i < v.size(); i++) {
			int k = i&-i;
			if (i == k) {
				double ang = 2 * PI * i / v.size();
				if (inv) ang *= -1;
				w[i] = base(cos(ang), sin(ang));
			}
			else w[i] = w[i - k] * w[k];
		}
		for (int i = 1, j = 0; i < v.size(); i++) {
			int bit = v.size() >> 1;
			for (; j >= bit; bit >>= 1) j -= bit;
			j += bit;
			if (i < j) swap(v[i], v[j]);
		}
		for (int i = 2; i <= v.size(); i <<= 1) {
			for (int j = 0; j < v.size(); j += i) {
				for (int k = 0; k < i / 2; k++) {
					base a = v[j + k], b = v[j + k + i / 2] * w[k * (v.size() / i)];
					v[j + k] = a + b;
					v[j + k + i / 2] = a - b;
				}
			}
		}
		if (inv) {
			for (int i = 0; i < v.size(); i++) {
				v[i] /= v.size();
			}
		}
	}
	vector <ll> mul(vector <ll> &v, vector <ll> &w) {
		vector<base> fv(v.begin(), v.end()), fw(w.begin(), w.end());
		int n = 1;
		while (n < max(v.size(), w.size())) n <<= 1;
		n <<= 1;
		fv.resize(n);
		fw.resize(n);
		FFT(fv, 0);
		FFT(fw, 0);
		for (int i = 0; i < n; i++) fv[i] *= fw[i];
		FFT(fv, 1);
		vector <ll> ret(n);
		for (int i = 0; i < n; i++) ret[i] = round(fv[i].real());
		return ret;
	}
	vector <ll> pw(vector <ll> &v) {
		vector<base> fv(v.begin(), v.end());
		int n = 1;
		while (n < v.size()) n <<= 1;
		n <<= 1;
		fv.resize(n);
		FFT(fv, 0);
		for (int i = 0; i < n; i++) fv[i] *= fv[i];
		FFT(fv, 1);
		vector <ll> ret(n);
		for (int i = 0; i < n; i++) ret[i] = round(fv[i].real());
		return ret;
	}
	vector <ll> mul(vector <ll> &v, vector <ll> &w, int b) {
		int n = 1;
		while (n < v.size() || n < w.size()) n <<= 1;
		n <<= 1;
		vector<base> v1(n), v2(n), v3(n), v4(n), r1(n), r2(n), r3(n);
		for (int i = 0; i < v.size(); i++) {
			v1[i] = base(v[i] / b, 0);
			v2[i] = base(v[i] % b, 0);
		}
		for (int i = 0; i < w.size(); i++) {
			v3[i] = base(w[i] / b, 0);
			v4[i] = base(w[i] % b, 0);

		}
		FFT(v1, 0); FFT(v2, 0); FFT(v3, 0); FFT(v4, 0);
		for (int i = 0; i < n; i++) {
			r1[i] = v1[i] * v3[i];
			r2[i] = v1[i] * v4[i] + v2[i] * v3[i];
			r3[i] = v2[i] * v4[i];

		}
		FFT(r1, 1); FFT(r2, 1); FFT(r3, 1);
		vector <ll> ret(n);
		for (int i = 0; i < n; i++) {
			ret[i] = (ll)round(r1[i].real()) * b * b + (ll)round(r2[i].real()) * b + (ll)round(r3[i].real());
		}
		return ret;
	}
}

int main() {
	int N, M; scanf("%d%d", &N, &M);
	vector <ll> a, b;
	for (int i = 0; i <= N; i++) {
		ll x; scanf("%lld", &x);
		a.push_back(x);
	}
	for (int i = 0; i <= M; i++) {
		ll x; scanf("%lld", &x);
		b.push_back(x);
	}
	vector <ll> ans = FFT::mul(a, b, (1 << 10));
	ll res = 0;
	for (int i = 0; i <= N + M; i++) res ^= ans[i];
	printf("%lld\n", res);
}

Compilation message

tt.cpp: In function 'void FFT::FFT(std::vector<std::complex<double> >&, bool)':
tt.cpp:15:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v.size(); i++) {
                     ^
tt.cpp:24:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1, j = 0; i < v.size(); i++) {
                            ^
tt.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 2; i <= v.size(); i <<= 1) {
                     ^
tt.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < v.size(); j += i) {
                      ^
tt.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < v.size(); i++) {
                      ^
tt.cpp: In function 'std::vector<long long int> FFT::mul(std::vector<long long int>&, std::vector<long long int>&)':
tt.cpp:48:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (n < max(v.size(), w.size())) n <<= 1;
            ^
tt.cpp: In function 'std::vector<long long int> FFT::pw(std::vector<long long int>&)':
tt.cpp:63:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (n < v.size()) n <<= 1;
            ^
tt.cpp: In function 'std::vector<long long int> FFT::mul(std::vector<long long int>&, std::vector<long long int>&, int)':
tt.cpp:75:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (n < v.size() || n < w.size()) n <<= 1;
            ^
tt.cpp:75:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (n < v.size() || n < w.size()) n <<= 1;
                            ^
tt.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v.size(); i++) {
                     ^
tt.cpp:82:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < w.size(); i++) {
                     ^
tt.cpp: In function 'int main()':
tt.cpp:104:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, M; scanf("%d%d", &N, &M);
                                 ^
tt.cpp:107:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll x; scanf("%lld", &x);
                          ^
tt.cpp:111:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll x; scanf("%lld", &x);
                          ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 6448 KB Output is correct
2 Correct 256 ms 36016 KB Output is correct
3 Correct 276 ms 36908 KB Output is correct
4 Correct 313 ms 36912 KB Output is correct
5 Correct 266 ms 36912 KB Output is correct
6 Correct 306 ms 36912 KB Output is correct
7 Correct 276 ms 36912 KB Output is correct
8 Correct 289 ms 36912 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 71724 KB Output is correct
2 Correct 1573 ms 139312 KB Output is correct
3 Correct 1406 ms 141360 KB Output is correct
4 Correct 3503 ms 280624 KB Output is correct
5 Correct 3376 ms 280624 KB Output is correct
6 Correct 3406 ms 280624 KB Output is correct
7 Correct 3453 ms 280624 KB Output is correct
8 Correct 3553 ms 280624 KB Output is correct