#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> poly;
typedef complex<double> base;
const double PI = acos(-1);
void fft(vector<base> &f, bool inv = 0){
int n = f.size(), j = 0;
for(int i=1; i<n; i++){
for(int k=(n>>1); (j^=k)<k; k >>= 1);
if(i < j) swap(f[i], f[j]);
}
double ang = 2*PI / n; if(inv) ang *= -1;
vector<base> root(n >> 1);
for(int i=0; i<root.size(); i++) root[i] = base(cos(ang * i), sin(ang * i));
for(int i=2; i<=n; i<<=1){
int st = n / i;
for(int j=0; j<n; j+=i) for(int k=0; k<(i>>1); k++){
auto u = f[j|k], v = f[j|k|(i>>1)] * root[st * k];
f[j|k] = u+v, f[j|k|(i>>1)] = u-v;
}
}
if(inv) for(int i=0; i<n; i++) f[i] /= n;
}
vector<ll> mul(vector<ll> _a, vector<ll> _b){
int n = 2; while(n < _a.size() + _b.size()) n <<= 1;
vector<base> a(n), b(n), r1(n), r2(n);
for(int i=0; i<_a.size(); i++) a[i] = base(_a[i] >> 10, _a[i] & 1023);
for(int i=0; i<_b.size(); i++) b[i] = base(_b[i] >> 10, _b[i] & 1023);
fft(a); fft(b);
for(int i=0; i<n; i++){
int j = i ? n-i : i;
auto f1 = (a[i] + conj(a[j])) / base(2, 0);
auto f2 = (a[i] - conj(a[j])) / base(0, 2);
auto f3 = (b[i] + conj(b[j])) / base(2, 0);
auto f4 = (b[i] - conj(b[j])) / base(0, 2);
r1[i] = f1 * (f3 + f4 * base(0, 1));
r2[i] = f2 * (f3 + f4 * base(0, 1));
}
fft(r1, 1); fft(r2, 1);
vector<ll> ans(n);
for(int i=0; i<n; i++){
ll a1 = roundl(r1[i].real());
ll a2 = roundl(r1[i].imag());
ll b1 = roundl(r2[i].real());
ll b2 = roundl(r2[i].imag());
ans[i] = b2 + ((a2 + b1) << 10) + (a1 << 20);
}
return ans;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
vector<ll> a(n+1), b(n+1);
for(auto &i : a) cin >> i;
for(auto &i : b) cin >> i;
auto res = mul(a, b);
ll ans = 0;
for(auto i : res) ans ^= i;
cout << ans;
}
Compilation message
tt.cpp: In function 'void fft(std::vector<std::complex<double> >&, bool)':
tt.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<root.size(); i++) root[i] = base(cos(ang * i), sin(ang * i));
~^~~~~~~~~~~~
tt.cpp: In function 'std::vector<long long int> mul(std::vector<long long int>, std::vector<long long int>)':
tt.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int n = 2; while(n < _a.size() + _b.size()) n <<= 1;
~~^~~~~~~~~~~~~~~~~~~~~~~
tt.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<_a.size(); i++) a[i] = base(_a[i] >> 10, _a[i] & 1023);
~^~~~~~~~~~
tt.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<_b.size(); i++) b[i] = base(_b[i] >> 10, _b[i] & 1023);
~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
3200 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
3328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
310 ms |
45820 KB |
Output is correct |
| 2 |
Incorrect |
330 ms |
47536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
