4089 大嘴乌鸦

题面

内容

大嘴乌鸦有 $n$ 个水瓶，第 $i$ 个水瓶重量为 $a_i$。

乌鸦要喝水，所以他找来了一堆石子，这些石子的重量的和为 $k$。

乌鸦发现，如果一个区间的水瓶的重量的异或和是他找的所有石子重量和的因子，则这个区间是一个合法的喝水区间。

乌鸦想知道，有多少个不同的喝水区间。

输入

第一行两个数字 $n$ 表示水瓶个数，以及石子的重量和 $k$。

第二行 $n$ 个正整数，第 $i$ 个数表示 $a_i$。

输出

一行一个整数表示有多少不同的喝水区间。

样例1

输入

5 3
1 2 3 4 5

输出

6

提示

样例 1 解释

总共有六个区间是合法的喝水区间，以下列举： $[1,1]$，$[1,2]$，$[1,5]$，$[2,3]$，$[3,3]$，$[4,5]$。

其异或和分别为：1，3，1，1，3，1。

数据范围

对于 $40 \%$ 的数据有 ：$n\le 10$。

对于 $80 \%$ 的数据有 ：$n\le 1000$。

对于 $100 \%$ 的数据有 ：$n\le 100000$，$1\le a_i,k\le n$。

思路

我们要找k%(sum[r]^sum[l-1])==0，我们可以先把k的因子记录一遍，存到v数组中，然后枚举这个因子v[j]，那么就是找sum[r]^sum[l-1]==v[j]，根据异或的性质，那么就是sum[l-1]==v[j]^sum[r]，因此我们只需要找到这个l的前缀异或和出现的次数就可以了。

而每经过一个点，就把它对应的前缀异或和出现的次数加一。

一个数的因子最多大概是$\sqrt(n)$个，因此复杂度是$O(n\sqrt(n))$。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int n,k,tot;
long long ans;
int a[N];
int cnt[N<<2];
int v[N];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
        if(k%i==0) v[++tot]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]^=a[i-1];
    }
    cnt[0]++;//假如第一位与k相同
    for(int i=1;i<=n;i++)//枚举右端点
    {
        for(int j=1;j<=tot;j++)
            ans+=cnt[a[i]^v[j]];//加上前面出现sum[l-1]的次数
        cnt[a[i]]++;//当前右端点出现次数+1
    }
    cout<<ans<<endl;
    return 0;
}