#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<double>;
const double PI = acos(-1);
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) {
double ang = 2 * PI / len * (inv ? -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 (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++;
vector<int> a(n), b(m);
for (auto& i : a) cin >> i;
for (auto& i : b) cin >> i;
vector<ll> res = multiply(a, b);
ll ans = 0;
for (auto& i : res) ans ^= i;
cout << ans << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
1148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
64 ms |
13896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
