LibreOJ #6439. Popcount Xor

发表于 阅读次数：

1. 题目描述

给定正整数 \(n\)，用二进制整数表示，求 \(\bigoplus_{i=0}^{n-1} \operatorname{popcount}(i)\)。保证 \(1 \le n \le 2^{3\times10^5}\)。

2. 思路

令 \(s\) 为输入的字符串，下标从 \(0\) 开始。枚举每个 \(s_i = 1\) 的 \(i\)，考虑第 \(0 \sim i-1\) 位已确定，第 \(i\) 位为 \(0\) 时对答案的贡献 \(c\)。则： \[ c = \bigoplus_{j=0}^{|s|-i+1} (cnt_{i-1}+j)\binom{|s|-i+1}{j} \bmod 2 \] 其中 \(cnt_i\) 表示从 \(s_0\) 到 \(s_i\) 中 \(1\) 的数量。\(\binom{|s|-i+1}{j}\) 是从后面的 \(|s|-i+1\) 位中选 \(j\) 位的方案数。模 \(2\) 是因为同一个数异或自己偶数次结果为 \(0\)。

由Lucas定理，\(\binom{n}{m} \bmod 2 = \binom{n\bmod2}{m\bmod2} \binom{\lfloor\frac{n}{2}\rfloor}{\lfloor\frac{m}{2}\rfloor} \bmod 2\)，不断将 \(n, m\) 一起右移一位，可得 \(\binom{n}{m} \bmod 2 = \prod_i \binom{n>>i \& 1}{m >> i \& 1}\)。

又由于 \(\binom{1}{1}=\binom{1}{0}=\binom{0}{0} = 1,\binom{0}{1} = 0\)，我们发现： \[ \binom n m \bmod 2 = [n \& m = m] \] 所以： \[ c = \bigoplus_{j=0}^{|s|-i+1} (cnt_{i-1}+j)[(|s|-i+1) \& j = j] \] 算这个式子的复杂度可以接受。

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size(), cnt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') continue;
        for (int j = n-i-1; ; j = (j-1)&(n-i-1)) {
            ans ^= (cnt+j);
            if (!j) break;
        }
        cnt++;
    }
    cout << ans << endl;
    return 0;
}

The End