#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace FFT {
typedef vector<complex<lld>> poly;
typedef complex<lld> cd;
const lld PI = acos(-1);
const cd I = {0, 1};
int lg; poly A, B;
vector<int> rev;
vector<poly> a;
void init_(vector<int> _a, vector<int> _b) {
lg = 32 - __builtin_clz(_a.size() +_b.size());
A.assign(1 << lg, {0, 0});
B.assign(1 << lg, {0, 0});
a.assign(1 << lg, poly());
rep(i, 0, signed(_a.size()) - 1) A[i] = _a[i];
rep(i, 0, signed(_b.size()) - 1) B[i] = _b[i];
rev.assign(1 << lg, 0);
rep(i, 0, (1 << lg) - 1) {
rep(j, 0, lg - 1) {
rev[i] <<= 1;
rev[i] |= ((i >> j) & 1);
}
}
}
poly fft(poly p, bool inv) {
rep(i, 0, (1 << lg) - 1) a[i].assign(1, p[i]);
rep(s, 1, lg) {
int len = 1 << (s - 1);
cd w = {1, 0};
cd it_w = exp(2 * PI * I / (lld)(2 * len));
if(inv) it_w = cd(1) / it_w;
for(int i = 0; i < (1 << lg); i += 2 * len) a[rev[i]].resize(2 * len);
rep(j, 0, len - 1) {
for(int i = 0; i < (1 << lg); i += 2 * len) {
int x = rev[i], y = rev[i + len];
cd t = a[y][j] * w;
a[x][j + len] = a[x][j] - t;
a[x][j] = a[x][j] + t;
}
w = w * it_w;
}
for(int i = len; i < (1 << lg); i += 2 * len) a[rev[i]].clear();
}
if(inv) for(auto &i : a[0]) i /= cd(1 << lg);
return a[0];
}
vector<int> solve() {
poly ans = poly(1 << lg, {0, 0});
A = fft(A, 0);
B = fft(B, 0);
rep(i, 0, (1 << lg) - 1) ans[i] = A[i] * B[i];
ans = fft(ans, 1);
vector<int> ans_int;
rep(i, 0, (1 << lg)- 1)
ans_int.push_back(round(abs(ans[i])));
return ans_int;
}
};
namespace solver {
int n, mx = 1000000;
vector<int> cnt;
void init_() {cnt.assign(mx + 1, 0);}
int solve() {
int ans = 0;
rep(i, 0, mx) if(cnt[i] & 1) ans ^= 2 * i;
FFT::init_(cnt, cnt);
vector<int> cnt1 = FFT::solve();
rep(i, 0, mx) cnt1[2 * i] -= (cnt[i] * cnt[i] / 2);
rep(i, 1, cnt1.size() - 1) {
cnt1[i] /= 2;
if(cnt1[i] & 1) ans ^= i;
}
return ans;
}
};
using namespace solver;
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n; cin >> n;
init_();
rep(i, 1, n) {
int x; cin >> x;
cnt[x] ++;
}
cout << solve() << "\n";
return 0;
}
Compilation message
xorsum.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
4 | #pragma loop-opt(on)
|
xorsum.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
xorsum.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
xorsum.cpp: In function 'long long int solver::solve()':
xorsum.cpp:6:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define rep(i, a, b) for(int i = a; i <= b; i ++)
......
98 | rep(i, 1, cnt1.size() - 1) {
| ~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp:98:3: note: in expansion of macro 'rep'
98 | rep(i, 1, cnt1.size() - 1) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
16236 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
163 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
163 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
16236 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
16236 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
