[原创]SPOJ SUBXOR - SubXor [Trie]【思维】

2017-03-25 12:38:34 Tabris_ 阅读数：422

博客爬取于2020-06-14 22:41:08
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/65935956

题目链接：http://www.spoj.com/problems/SUBXOR/en/

————————————————————————————————————————————
SUBXOR - SubXor
no tags
A straightforward question. Given an array of positive integers you have to print the number of subarrays whose XOR is less than K.
Subarrays are defined as a sequence of continuous elements Ai, Ai+1, …, Aj . XOR of a subarray is defined as Ai^Ai+1^ … ^Aj.
Symbol ^ is Exclusive Or. You can read more about it here:
http://en.wikipedia.org/wiki/Exclusive_or

Input Format:

First line contains T, the number of test cases. Each of the test case consists of N and K in one line, followed by N space separated integers in next line.

Output Format:

For each test case, print the required answer.

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5
1 ≤ K ≤ 10^6
Sum of N over all testcases will not exceed 10^5.

Sample Input:

1
5 2
4 1 3 2 7
Sample Output:

3
Explanation:

Only subarrays satisfying the conditions are [1],[1,3,2] and [3,2].

————————————————————————————————————————————
题目大意:
给你一个序列,问你有多少个区间的所有元素异或和小于k

解题思路:

首先我们很容易想到,
对于一个区间异或和 可以先预处理出前缀异或和pre[],这样的话区间[l,r]\big[l,r\big]的异或和成就变成了pre[r]^pre[l-1]

现在问题就变成了序列中选取两个元素异或结果小于K的方案数有多少了

如果是等于k的话 相信大家都会做了,但是要小于k怎么处理呢 ,
其实一样的 ,只是在计算等于K的过程中进行统计,对于k当前二进制位下为1的时候我们就记录下和当前位异或为0的组合有多少 ,然后遍历下去重复此过程就好了,

注意要把pre[0]先插入字典树,这样才能统计区间[1(数字),r]\big[1(数字),r\big]的结果

附本题代码
————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# include <bits/stdc++.h>

typedef long long int LL ;
using namespace std;
const int N   = 1e5+7;
const int MOD = 1000000007;
/*******************************************************/
int trie[N*20][2],val[N*20],cnt;
int _,n,k;
void insert(int a){
    int now = 0,bt;
    for(int i=20;i>=0;i--){
        bt = (a&(1<<i))?1:0;
        if(!trie[now][bt])   trie[now][bt]=++cnt;
        now = trie[now][bt];
        val[now]++;
    }
}

LL query(int a){
    LL ans = 0;
    int now = 0,bt,bk;
    for(int i=20;i>=0;i--){
        bk = (k&(1<<i))?1:0;
        bt = (a&(1<<i))?1:0;

        if(bk){
            ans+=val[trie[now][bt]];
            if(!trie[now][1-bt]) break;
            now = trie[now][1-bt];
        }
        else {
            if(!trie[now][bt]) break;
            now = trie[now][bt];
        }
    }
    return ans;
}

int a[N];

void init(){
    cnt = 0;a[0]=0;
    memset(trie,0,sizeof(trie));
    memset(val,0,sizeof(val));
}

int main(){
//    printf("%d\n",1<<20);

    scanf("%d",&_);
    while(_--){
        init();LL ans = 0;
        scanf("%d%d",&n,&k);
        insert(0);                               //!!!!!!!
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            a[i]^=a[i-1];
            ans+=query(a[i]);
            insert(a[i]);
        }
//        for(int i=1;i<=n;i++)printf("%d%c",a[i],(i==n)?'\n':' ');
        printf("%lld\n",ans);
    }
    return 0;
}

/***
1
5 2
4 1 3 2 7
*/