#include <cstdio>
#define _USE_MATH_DEFINES
#include <math.h>
#include <complex>
#include <vector>
#include <algorithm>
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
typedef complex<double> base;
typedef long long ll;
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 * M_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<int> &a, const vector<int> &b, vector<long long> &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] = (ll)(fa[i].real() + (fa[i].real()>0 ? 0.5 : -0.5));
ll r = res[0];
for (int i = 1; i < n; i++) r ^= res[i];
printf("%lld", r);
}
int n, m, x;
int main() {
scanf("%d%d", &n, &m);
vector <int> a(n + 1), b(m + 1);
vector <ll> res;
for (int i = 0; i <= n; i++) scanf("%d", &a[i]);
for (int i = 0; i <= m; i++) scanf("%d", &b[i]);
multiply(a, b, res);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1676 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1676 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
1676 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
