This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef complex<double> base;
typedef long long lld;
const double PI = atan2(0, -1);
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*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<lld> &a, const vector<lld> &b, vector <lld> &res)
{
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);
res.resize(n);
for (int i=0;i<n;i++) res[i] = int(fa[i].real() + (fa[i].real() > 0 ? 0.5 : -0.5));
}
void my_fft(const vector<lld> &a, const vector<lld> &b, vector <lld> &res)
{
int n = max(sz(a), sz(b));
vector <lld> fa, fb;
for (int i=0;i<n;i++) fa.pb(0), fb.pb(0);
for (int t: a) fa.pb(t);
for (int t: b) fb.pb(t);
for (int i=0;i<n;i++) fa.pb(0), fb.pb(0);
vector <lld> tmp;
multiply(fa, fb, tmp);
res.clear();
for (int i=0;i<n+n-1;i++) res.pb(tmp[i+n+n]);
}
int N, M;
int main()
{
scanf("%d%d", &N, &M);
vector <lld> a, b;
for (int i=0;i<=N;i++){
int x; scanf("%d", &x); a.pb(x);
}
for (int i=0;i<=M;i++){
int x; scanf("%d", &x); b.pb(x);
}
vector <lld> val;
my_fft(a, b, val);
lld ans = 0;
for (int i=0;i<=N+M;i++) ans ^= val[i];
printf("%lld\n", ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |