题解：P17189 [ICPC 2017 Hong Kong R] Count the Even Integers

· · 题解

~生成函数做法~

题目要求杨辉三角形前 N 行的偶数个数，为此，先考虑第 n 行的奇数个数．

熟知

[x^k](1+x)^n = \dbinom{n}{k},

这里 [x^k]f(x) 表示 f(x) 中 x^k 的系数．

因此只需要考虑

(1+x)^n \pmod 2

中非零系数的个数，记结果为 C(n)．

显然 n=0 时上式非零系数个数为 C(0)=0；n=1 时上式中非零系数个数为 C(1)=1．

考虑

(1+x)^{2n} \pmod 2,

注意到在 \bmod~2 意义下，(a+b)^2\equiv a^2+b^2，因此

(1+x)^{2n} \equiv (1+x^2)^{n} \pmod 2,

即

C(2n) = C(n).

同理

(1+x)^{2n+1} \equiv (1+x)(1+x^2)^{n} \pmod 2,

由于 (1+x^2)^{n} 中只包含偶数次幂，因此

C(2n+1) = 2\cdot C(2n) = 2\cdot C(n).

数学归纳可知

C(n) = 2^{\operatorname{popcount}(n)},

这里 \operatorname{popcount}(n) 表示 n 二进制表示中 1 的数量．

故题目所求即为

\dfrac{(N+1)(N+2)}{2} - \sum_{n=0}^{N} 2^{\operatorname{popcount}(n)}.

记

S(N) = \sum_{n=0}^{N} 2^{\operatorname{popcount}(n)},

考虑将 [0,N]\cap \mathbb{N} 划分为若干不交子集，方便求和．

设 N 的二进制展开为

N = \sum_{i=0}^m b_{i}2^{i} \quad b_i\in\{0,1\},b_m=1,

其中 m = \left\lfloor\log_2 N\right\rfloor，并称 b_i 为 N 的第 i 位．

对于每个 b_i=1，考虑满足如下条件的 n：

显然这些 n 构成集合

R(i) = \left[\sum_{k=i+1}^{m}b_{k}2^{k},\sum_{k=i+1}^{m}b_{k}2^{k}+2^{i}\right) \cap \mathbb{N}.

注意到这些集合与 \{N\} 构成了 [0,N]\cap\mathbb{N} 的一个划分．

对于上述每个集合，其对 S(N) 的贡献为

\sum_{x \in R(i)}2^{\operatorname{popcount}(x)}=\sum_{k=0}^{2^{i}-1} 2^{\sigma_{i}+\operatorname{popcount}(k)}

这里 \sigma_i = \sum\limits_{k=i+1}^{m}b_k 表示高位 1 的数量．

其中，由于 2^{\operatorname{popcount}(n)} 等价于为 n 的每个为 1 的位贡献因子 2，为每个为 0 的位贡献因子 1，因此根据乘法分配律，有

\sum_{k=0}^{2^{i}-1} 2^{\operatorname{popcount}(k)} = (2+1)^{i} = 3^{i}

亦可注意到这个式子等价于 子集遍历 的枚举量．

因此

\sum_{x \in R(i)}2^{\operatorname{popcount}(x)} = 2^{\sigma_{i}}\cdot 3^{i}.

故

S(N) = \sum_{i=0}^{m}b_i2^{\sigma_i}3^i + 2^{\operatorname{popcount}(N)}.

由于 N 最大为 10^{50}，这里使用 Python 解决．

import sys

for N in map(int, sys.stdin.read().split()):
    ans = 0
    high_popcnt = 0
    m = len(bin(N)) - 2
    for i in range(m, -1, -1):
        if N & (1 << i):
            ans += (3 ** i) << high_popcnt
            high_popcnt += 1
    ans += (1 << high_popcnt)
    print((N + 1) * (N + 2) // 2 - ans)

为没有 Python 基础的同学简单解释几句：

你们当伪代码看也行．