Codeforces Round #841 (Div. 2) and Divide by Zero【异或差分+动态map维护】 2022 C. Even Subarrays

客官°小女子只卖身不卖艺 2024-03-30 12:43 40阅读 0赞

[Problem - C - Codeforces][]

题意：

给定一个数列，统计有多少子串的异或和的约数个数是偶数

思路：

首先，关于约数个数：

当提及约数个数时，可以去想想唯一分解定理

当约数个数为奇数时，它一定是个完全平方数，当约数个数为偶数时，它一定不是完全平方数

因此我们可以去考虑问题的反面，去统计约数个数是奇数时的区间个数

即去统计区间异或和是完全平方数的区间个数

那么，我们怎么去**查找区间异或和为定值的区间**

设左边界对应的异或和是y

那么有：

s\[i\]^y=x

即：s\[i\]^y^s\[i\]=x^s\[i\]

即：y=x^s\[i\]

这里是个小trick：先去预处理前缀异或和s\[i\]，假设区间异或和为x，那么左边界就是s\[i\]^x

这个其实就是差分，只不过从加法变成了异或

因此，我们去枚举前缀，然后去枚举完全平方数，对于这个完全平方数，我们可以O(1)求出左边界s\[i\]^x ，把右边界放map里面统计就好了，这里的map其实是线性地动态维护

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10,mod=1e9+7;
    vector<int> v;
    int n;
    int s[mxn],mp[mxn];
    void solve(){
    	cin>>n;
    	int ans=n*(n+1)/2;
    	mp[0]++;
    	for(int i=1;i<=n;i++) cin>>s[i],s[i]^=s[i-1];
    	for(int i=1;i<=n;i++){
    		for(auto it:v) ans-=mp[s[i]^it];
    		mp[s[i]]++;
    	}
    	cout<<ans<<'\n';
    	for(int i=0;i<=n;i++) mp[s[i]]--;
    }
    void init(int n){
    	for(int i=0;i*i<=n;i++) v.push_back(i*i);
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	init(5e5);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

**总结：**

**当提及约数个数时，可以去想想唯一分解定理**

**当约数个数为奇数时，它一定是个完全平方数，当约数个数为偶数时，它一定不是完全平方数**

**如何查找区间异或和为定值的区间：**

**先去预处理前缀异或和s\[i\]，假设区间异或和为x，那么左边界就是s\[i\]^x**

[Problem - C - Codeforces]: https://codeforces.com/contest/1731/problem/C