由于题目要求的是两个连续的区间,下文会称其为左右区间,我们可以枚举右区间的起点,不断往右扩展,每次答案加上 与右区间异或和相等 的左区间的个数 即可。
如何处理左区间,每次枚举右区间起点的时候,我们令右区间起点的前一个数为左区间的终点,往左边扫描,加入新的区间值,由于题目给的元素大小不超过1e5,可以开数组存,如果元素大小过大,用map也是可以的,复杂度为n^2log(n)也可以过1000的数据。
#include <cctype> #include <cfloat> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <algorithm> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <istream> #include <iterator> #include <list> #include <map> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #include <unordered_map> #include <unordered_set> using namespace std; const int maxn=1005; int A[maxn]; map<int,int> M; int main() { int n; cin>>n; for (int i=1; i<=n; i++) { cin>>A[i]; A[i]^=A[i-1]; } long long ans=0; for (int i=1; i<=n; i++) { for (int j=0; j<i; j++) M[A[i]^A[j]]++; for (int j=i+1; j<=n; j++) ans+=M[A[j]^A[i]]; } printf("%lld\n",ans); return 0; }