Submission #21417

#	Time	Username	Problem	Language	Result	Execution time	Memory
21417		gs14004	씽크스몰 (kriii3_TT)	C++11	30 / 30	3223 ms	281228 KiB

tt

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

static char _buffer[1 << 19];
static int _currentChar = 0;
static int _charsNumber = 0;

static inline int _read() {
	if (_charsNumber < 0) {
		exit(1);
	}
	if (!_charsNumber || _currentChar == _charsNumber) {
		_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), stdin);
		_currentChar = 0;
	}
	if (_charsNumber <= 0) {
		return -1;
	}
	return _buffer[_currentChar++];
}

static inline int _readInt() {
	int c, x, s;
	c = _read();
	while (c <= 32) c = _read();
	x = 0;
	s = 1;
	if (c == '-') {
		s = -1;
		c = _read();
	}
	while (c > 32) {
		x *= 10;
		x += c - '0';
		c = _read();
	}
	if (s < 0) x = -x;
	return x;
}
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 * M_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<lint> multiply(vector<lint> &v, vector<lint> &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<lint> ret(n);
		for(int i=0; i<n; i++) ret[i] = round(fv[i].real());
		return ret;
	}
	vector<lint> power(vector<lint> &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<lint> ret(n);
		for(int i=0; i<n; i++) ret[i] = round(fv[i].real());
		return ret;
	}
	vector<lint> multiply(vector<lint> &v, vector<lint> &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<lint> ret(n);
		for(int i=0; i<n; i++){
			ret[i] = (lint)round(r1[i].real()) * b * b + (lint)round(r2[i].real()) * b + (lint)round(r3[i].real());
		}
		return ret;
	}
}
int n, m;
vector<lint> v, w;

int main(){
	n = _readInt();
	m = _readInt();
	for(int i=0; i<=n; i++){
		v.push_back(_readInt());
	}
	for(int i=0; i<=m; i++){
		w.push_back(_readInt());
	}
	auto poly = fft::multiply(v, w, 1024);
	lint ret = 0;
	for(int i=0; i<=n+m; i++){
		ret ^= poly[i];
	}
	cout << ret;
}

Compilation message (stderr)

tt.cpp: In function 'void fft::fft(std::vector<std::complex<double> >&, bool)':
tt.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size(); i++){
                 ^
tt.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1,j=0; i<v.size(); i++){
                     ^
tt.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=2; i<=v.size(); i<<=1){
                 ^
tt.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<v.size(); j+=i){
                  ^
tt.cpp:71:18: 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::multiply(std::vector<long long int>&, std::vector<long long int>&)':
tt.cpp:79:11: 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::power(std::vector<long long int>&)':
tt.cpp:94:11: 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::multiply(std::vector<long long int>&, std::vector<long long int>&, int)':
tt.cpp:106:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(n < v.size() || n < w.size()) n <<= 1;
           ^
tt.cpp:106:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(n < v.size() || n < w.size()) n <<= 1;
                           ^
tt.cpp:109:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size(); i++){
                 ^
tt.cpp:113:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<w.size(); i++){
                 ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10