题解|#小美的区间异或和#
小美的区间异或和
https://ac.nowcoder.com/acm/problem/259733
首先读懂题目，题目要求的是所有连续子数组的权值和。二权值和为数组中人选出连个数的异或之和。由于是异或运算所以对于某个数上某位二进制数为0与之前的连续区间里面能凑成多少个1取决于前面有多少少个1，还要注意的是从第一个数到这个数之间的区间也可以分成子区间，那就是说假如前一位的是1的话，那么回和前面的位异或上前面为的编号次，也就是i+1次。如果我们自己某一位二进制可以和前面凑成多少个1，那么在这一位直接按这一位的二进制值乘上个数即可。
如何维护个数：对于2,3,1这个序列来说，从1来看的话他构成的子数组为[2,3,1]和[3,1]，所以前面的3里面的数其实是被异或相加了两次。有了这个规律开一个二维数组去维护每一位上0或1的个数。然后算出每一位数与之前面凑成的序列的值。最后相加即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5+10;
const int mod = 1e9+7;
int dp[maxn];
//记录前面有多少个1或者有多少个0。
int cnt[maxn][2];
signed main() {
int n;
cin>>n;
vector<int> a(n);
for (int i=0;i<n;i++) {
scanf("%lld", &a[i]);
}
for (int i=0;i<n;i++) {
//当前的下标能够组成的值里面有前面i的一份
dp[i+1] = dp[i];
for (int j=0;j<31;j++) {
//对每一位进行二进制位数下的判断。
int ok = (a[i]>>j)&1;
dp[i+1] = (dp[i+1]%mod + ((1<<j)*cnt[j][1-ok])%mod)%mod;
cnt[j]
= (cnt[j]+i+1)%mod;
}
}
int ans = 0;
for (int i=1;i<=n;i++) {
ans = (ans%mod+dp[i]%mod)%mod;
}
cout<<ans;
return 0;
}
投递美团等公司10个岗位 >