平台门户网站建设方案,厦门seo屈兴东,网站开发推广招聘,网站建设管理和运行维护制度题目描述
给定一个数组 Ai#xff0c;分别求其每个子段的异或和#xff0c;并求出它们的和。
或者说#xff0c;对于每组满足 1≤L≤R≤n 的 L#xff0c;R求出数组中第 L 至第 R 个元素的异或和。
然后输出每组 L#xff0c;R 得到的结果加起来的值。
输入格式
输入…题目描述
给定一个数组 Ai分别求其每个子段的异或和并求出它们的和。
或者说对于每组满足 1≤L≤R≤n 的 LR求出数组中第 L 至第 R 个元素的异或和。
然后输出每组 LR 得到的结果加起来的值。
输入格式
输入的第一行包含一个整数 n。
第二行包含 n 个整数 Ai相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
5
1 2 3 4 5
样例输出
39 知识点前缀和与差分 代码
通过90%测试样例代码
//0和任意数x异或都是x
//x和x异或得到0
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N100010;
ll a[N],b[N],sum;
int main()
{ll n;cinn;for(int i1;in;i){cina[i];b[i]b[i-1]^a[i];}for(int i1;in;i){for(int ji;jn;j){sumb[i-1]^b[j];//前半部分异或抵消}}coutsumendl;return 0;
} 通过100%测试样例代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N100010;
ll a[N],b[N],c[N],cnt;
int main() {ll n;cinn;for(int i1;in;i) {cina[i];}for(int i0;i20;i) {int one0,zero0,sum0;for(int j1;jn;j){b[j](a[j]i)0x1;c[j]c[j-1]^b[j];//前缀异或数组按位 if(c[j]1){one;}}zeron-one;//one*zero的值为前缀异或数组中1的数量乘0的数量 //one为前缀异或数组中1的数量 sumone*zeroone;cnt(pow(2,i)*sum); }coutcntendl;return 0;
}
