题目大意就是寻找区间s[i..j]使得s[i]xor s[i+1]...xor s[j]=k
咱首先了解一个性质 a xor b xor b=a,也就是说异或相同的东西就变成了0,然后a 异或之就是还是等于a,那么我们把这个结论运用到这道题目中,假设有 s[i..j]满足异或和为0,那么 s[1..i-1] xor s[i..j] xor k 会等于什么呢?显然会等于s[1..i-1],也就是说假设我们固定了右端点,那么 所有满足异或和为K的i必有 s[1..i-1]=s[1..j] xor k,那么我们可以枚举右端点j,然后求满足s[1..i-1]=s[1..j] xor k的i有多少个就可以了,怎么做呢?最快的方法当然就是用HASH毫无压力,初始值不超过10000,10000最多14位,我们只需要将HASH表开到16384就可以了,然后读入的时候处理每一个前缀异或和,将它插入HASH表中,然后我们枚举j,算出s[1..i-1]的值p,然后直接让ans加上hash[p]就可以了。
注意要先更新ans再将s[i]插入,不然会将s[i+1,i]这种算进去的。
========================================================================
program xorr;
var hash:array[0..16384]of longint;
s:array[0..5000]of longint;
n,k:longint;
procedure init;
var i,j,p:longint;
ans:longint;
begin
read(n,k);
fillchar(hash,sizeof(hash),0);
s[0]:=0; ans:=0;
inc(hash[s[0]]);
for i:=1 to n do
begin
read(j);
s[i]:=s[i-1] xor j;
p:=s[i] xor k;
inc(ans,hash[p]);
inc(hash[s[i]]);
end;
write(ans);
end;
begin
init;
end.
评论