Home_W的位运算4

TimeLimit:2000MS  MemoryLimit:128MB

64-bit integer IO format:

%I64d

Problem Description

给定一个序列 a1,a2……an

求有多少个对l,r(l<=r),满足 al ^ a(l+1) ^ a(l+2) ^…… ^ ar = s，其中^代表按位异或

 

Input

只有一组数据

第一行是一个整数n

接下来一行有n个整数，分别代表 a1,a2……an

再接下整数q代表查询次数

接来下来有q行，每行是一个整数代表s

其中0<n,s,ai<=10^6

q<=10

 

Output

对于每个s，输出有多少对l,r满足题目要求

 

SampleInput

42 2 4 171234567

SampleOutput

1202211 思路：由n的范围来确定了暴力是不能解决问题的，所以我们要预处理优化，将s[0]=0,因为0^x=x; s[1]=s[0]^a1; s[2]=s[1]^a2; ............ 有了预处理以后，我们还要知道一点 al ^ a(l+1) ^ a(l+2) ^…… ^ ar = s则s[r]^s[l]=s; 且s[l]^s=s[r],在这个基础上我们就可以用O(n)遍历每一个s[i]，且得到有多少个s[i]^s在预处理的数组里出现过； 也就是我们只要求出对每一个s[i]有几个s[r]满足s[r]^s[l]=s； 下面献上我low逼的代码

时间：748MS

长度：275

1     scanf("%I64d", &n);2     for(i=1; i<=n; i++)3     {4         scanf("%I64d", &s[i]);5         s[i]=s[i]^s[i-1];///预处理的关键步骤16         z[s[i]]++;///预处理的关键步骤2，且值得注意的是z[0]=1要在循环之前赋值一遍7     }

scanf("%I64d", &s);        for(i=0; i<=n; i++)            sum+=z[s[i]^s];        printf("%I64d\n", sum/2);///因为s[l]^s=s[r],s[r]^s=s[l];所以用/2可以解决问题；