异或序列

Solution

非常板的一道题。

看到区间异或和就能想到转换为前缀异或,即

\[\sum_{i=1}^n \sum_{j=0}^{i-1} s_i \oplus s_j \]

又想到位运算各位之间互不干涉,所以想到按位来考虑。以其中一位为例,能构成一个 01 序列,对它做前缀异或后,记为 \(b_i\)。那么 \(b_i\) 的贡献就是

\[\sum_{j=0}^{i-1} [b_j\oplus b_i=1] \]

所以只需要统计前缀 0 和 1 的个数,随便更新一下答案就可以了。

上一篇:HDU4388-Stone Game II-Nim变形


下一篇:CF1408