ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190562 | #3380. xor | mH | 100 | 534ms | 1252kb | C++11 | 1.1kb | 2023-10-06 11:00:19 | 2023-10-06 12:01:39 |
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
int m, ans, cnt, p[35];
void insert(int x)
{
for (int i = 32; ~i; i--)
if (x & (1ll << i))
if (!p[i])
{
p[i] = x;
return;
}
else
x ^= p[i];
}
void rebuild()
{
for (int i = 32; ~i; i--)
for (int j = i - 1; ~j; j--)
if (p[i] & (1ll << j))
p[i] ^= p[j];
for (int i = 0; i <= 32; i++)
if (p[i])
p[cnt] = p[i], cnt++;
}
void dfs(int res, int now)
{
if (res == cnt - 2)
{
ans += (now ^ p[res] ^ p[res + 1]) + (now ^ p[res + 1]) + (now ^ p[res]) + now;
return;
}
dfs(res + 1, now);
dfs(res + 1, now ^ p[res]);
}
void dfs1(int res, int now)
{
if (res == cnt)
{
ans += now;
return;
}
dfs1(res + 1, now);
dfs1(res + 1, now ^ p[res]);
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("data/data.in", "r", stdin);
// freopen("data/data.out", "w", stdout);
#endif
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> m;
while (m--)
{
int now;
cin >> now;
insert(now);
}
rebuild();
if (cnt > 20)
dfs(0, 0);
else
dfs1(0, 0);
cout << ans;
exit(0);
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1244kb
input:
1 0
output:
0
result:
ok single line: '0'
Test #2:
score: 10
Accepted
time: 15ms
memory: 1248kb
input:
100000 65921 198375 21586 38561 397862 231047 214055 475329 133011 759024 181248 331796 677542 10327...
output:
68047798272
result:
ok single line: '68047798272'
Test #3:
score: 10
Accepted
time: 16ms
memory: 1248kb
input:
100000 677027 820321 557474 70635 668211 742187 333000 807730 553720 880897 448250 504907 37563 2146...
output:
137169862656
result:
ok single line: '137169862656'
Test #4:
score: 10
Accepted
time: 18ms
memory: 1248kb
input:
100000 19965 479774 56172 281200 333015 35825 447368 476544 476331 513079 465656 312879 511426 82975...
output:
67645603840
result:
ok single line: '67645603840'
Test #5:
score: 10
Accepted
time: 21ms
memory: 1252kb
input:
100000 857727 839078 518837 441723 868634 712311 149274 174410 910286 290333 165547 1019132 415544 1...
output:
274877644800
result:
ok single line: '274877644800'
Test #6:
score: 10
Accepted
time: 21ms
memory: 1248kb
input:
100000 508190 818044 445053 771099 163392 437294 982637 725539 88101 831756 736077 289071 492073 993...
output:
274844090368
result:
ok single line: '274844090368'
Test #7:
score: 10
Accepted
time: 136ms
memory: 1252kb
input:
100000 354185019 666591573 788482649 1053188434 745934094 29050950 850330965 44770138 672555111 1038...
output:
72055111479721984
result:
ok single line: '72055111479721984'
Test #8:
score: 10
Accepted
time: 33ms
memory: 1248kb
input:
100000 168692682 146806924 180981378 441140484 479478730 378569246 306272158 234996946 206638618 513...
output:
4345200948281344
result:
ok single line: '4345200948281344'
Test #9:
score: 10
Accepted
time: 137ms
memory: 1252kb
input:
100000 592447371 856214398 558635630 352846294 538016599 589357573 892700581 318770198 913614510 684...
output:
62478648669634560
result:
ok single line: '62478648669634560'
Test #10:
score: 10
Accepted
time: 137ms
memory: 1248kb
input:
100000 864560252 956306323 403708676 410585270 67247857 394338323 943268623 779170496 587868844 2817...
output:
72036703249891328
result:
ok single line: '72036703249891328'