题目描述
给定一个数组 Ai
,分别求其每个子段的异或和,并求出它们的和。
或者说,对于每组满足 1≤L≤R≤n
的 L,R
,求出数组中第 L
至第 R
个元素的异或和。
然后输出每组 L,R
得到的结果加起来的值。
输入格式
输入的第一行包含一个整数 n
。
第二行包含 n
个整数 Ai
,相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 30%
的评测用例,n≤300
;
对于 60%
的评测用例,n≤5000
;
对于所有评测用例,1≤n≤105
,0≤Ai≤220
。
输入样例:
5
1 2 3 4 5
输出样例:
39
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N],s[N];
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
s[i] = s[i - 1] ^ a[i];
}
LL ans = 0;
for(int i = 1;i <= n;i++)
{
for(int j = 0;j < i;j++)
{
ans += (LL)s[i] ^ s[j];
}
}
printf("%lld\n",ans);
return 0;
}
----------
算法2
(贡献法) $O(20 * n)$
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N];
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
}
LL ans = 0;
for(int i = 0;i <= 19;i++)
{
int n0 = 1; //这个就是第i位上到第j个位置偶数个1的区间的个数。
int n1 = 0; //同上,为奇数个1的区间的个数。
int s = 0; //统计目前一共出现的1的个数。
for(int j = 1;j <= n;j++)
{
if((a[j] >> i) & 1) s++;
if(s % 2) //当前位为奇数个1,会使得奇数个1的区间加1。
{
ans += (LL)(1 << i) * n0;
n1++;
}
else //当前位为偶数个1,会使得偶数个1的区间加1。
{
ans += (LL)(1 << i) * n1;
n0++;
}
}
}
printf("%lld\n",ans);
return 0;
}
参考哔哩哔哩中某位大佬链接如下所示:https://www.bilibili.com/video/BV1NK421b7DA/?spm_id_from=333.337.search-card.all.click&vd_source=292c83f2ec29c73a1f98cb1ee27248e7
讲解的十分详细,可以理解。
```
给我点个赞吧!