题意:
给定一个长度为n的整数数组,问有多少对互不重叠的非空区间,使得两个区间内的数的异或和为0。
N<1e3
题解:
如果直接暴力枚举两个区间的话 复杂度为O(n^4),显然不行。
观察一下数据范围,可以得到本题能够支持O(n^2)的做法,所以我们想怎么枚举一个区间能得到答案。
那么假设当前枚举的区间[i,j]两个区间中 右边的那一个,所以我们只需要知道 i 的左边有多少个区间的异或值和当前区间相等即可,我们用cnt数组表示出现次数。
这一部分我们可以动态维护:每次新加入一个数i时,他的贡献就为以他为右端点的异或值,那么我们每将i+1的时候就把以他为右端点的所有区间的异或值+1即可
复杂度O(n^2)
dai
#pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #define yes puts("YES") #define no puts("NO") #define ios ios::sync_with_stdio(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef vector<int> VI; const int maxn = 1e6 + 6; const LL inf = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;} LL inv(LL x){return qp(x,mod-2);} int _,n,a[maxn],cnt[maxn],pre[maxn]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) pre[i]=a[i]^pre[i-1]; LL ans=0; for(int i=1;i<=n;i++){ for(int j=i-1;j>=1;j--) cnt[pre[i-1]^pre[j-1]]++; for(int j=i;j<=n;j++){ ans+=cnt[pre[j]^pre[i-1]]; //cout<<ans<<','<<i<<','<<j<<endl; } } printf("%lld\n",ans); }