#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define a3 array<int, 3>
#define MP make_pair
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = (1 << 20);
const int oo = 2e9;
unordered_map<ull, int> mem[N];
ull vl[N], ans = 0;
int m, n, a[N];
mt19937_64 rnd(chrono::system_clock().now().time_since_epoch().count());
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> m;
n = (1 << m);
if (m == 1){
cout << 2;
return 0;
}
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++){
int obr = ((n - 1) ^ i);
if (obr < i) continue;
vl[i] = rnd();
vl[obr] = ull(0) - vl[i];
}
mem[0][0]++;
ull sum = 0;
int xr = 0;
for (int i = 0; i < n; i++){
sum += vl[a[i]];
xr ^= a[i];
ans += mem[xr][sum];
mem[xr][sum]++;
}
cout << ull(n) * (ull(n) + 1) / 2 - ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
57848 KB |
Output is correct |
2 |
Correct |
39 ms |
57976 KB |
Output is correct |
3 |
Correct |
39 ms |
57856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
57856 KB |
Output is correct |
2 |
Correct |
40 ms |
57856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
57984 KB |
Output is correct |
2 |
Correct |
42 ms |
58112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
58240 KB |
Output is correct |
2 |
Correct |
43 ms |
58360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
59000 KB |
Output is correct |
2 |
Correct |
46 ms |
58624 KB |
Output is correct |
3 |
Correct |
45 ms |
58488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
76 ms |
62124 KB |
Output is correct |
2 |
Correct |
63 ms |
61304 KB |
Output is correct |
3 |
Correct |
90 ms |
64760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
72 ms |
62072 KB |
Output is correct |
2 |
Correct |
81 ms |
65016 KB |
Output is correct |
3 |
Correct |
171 ms |
72696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
75000 KB |
Output is correct |
2 |
Correct |
136 ms |
72020 KB |
Output is correct |
3 |
Correct |
160 ms |
71544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
804 ms |
126408 KB |
Output is correct |
2 |
Correct |
730 ms |
124528 KB |
Output is correct |
3 |
Correct |
339 ms |
102904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
709 ms |
126328 KB |
Output is correct |
2 |
Correct |
476 ms |
114788 KB |
Output is correct |
3 |
Correct |
541 ms |
114264 KB |
Output is correct |
4 |
Correct |
708 ms |
125432 KB |
Output is correct |