UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190562#3380. xormH100534ms1252kbC++111.1kb2023-10-06 11:00:192023-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'