#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
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++){
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2584 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2584 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2584 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2900 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2876 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2876 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2876 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2876 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
7052 KB |
Output is correct |
| 2 |
Correct |
229 ms |
36620 KB |
Output is correct |
| 3 |
Correct |
226 ms |
37512 KB |
Output is correct |
| 4 |
Correct |
243 ms |
37516 KB |
Output is correct |
| 5 |
Correct |
233 ms |
37516 KB |
Output is correct |
| 6 |
Correct |
229 ms |
37516 KB |
Output is correct |
| 7 |
Correct |
243 ms |
37516 KB |
Output is correct |
| 8 |
Correct |
239 ms |
37516 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
526 ms |
72328 KB |
Output is correct |
| 2 |
Correct |
1399 ms |
139916 KB |
Output is correct |
| 3 |
Correct |
1319 ms |
141964 KB |
Output is correct |
| 4 |
Correct |
3223 ms |
281228 KB |
Output is correct |
| 5 |
Correct |
3203 ms |
281228 KB |
Output is correct |
| 6 |
Correct |
2989 ms |
281228 KB |
Output is correct |
| 7 |
Correct |
3143 ms |
281228 KB |
Output is correct |
| 8 |
Correct |
2993 ms |
281228 KB |
Output is correct |
