sequence

2014年10月31日1,1551

给定一个序列,求其所有区间 按位异或的值 的和

题解

按位考虑。。。

比如说对于每个a[i]的第K位

对于一个x,假设得到了i到x-1(i<x)这些区间的异或值。。。即有f0[x-1]个0,f1[x-1]个1,每个1

对答案的贡献是1<<(K-1)

那么对于i到x,仅仅是对于所有区间加入了a[x]这个元素

以及多了仅含a[x]的区间。。

所以若a[x]=1的话,f0[x]=f1[x-1],f1[x]=f0[x-1]+1

否则f0[x]=f0[x-1]+1,f1[x]=f1[x-1]

 

  • vivym2014年10月31日 下午8:36 回复

    Orz……

    #1