HDUOJ 4349 - Xiao Ming's Hope

题面

给定 nn,求组合数 (n0),(n1),,(nn)\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}n+1n + 1 个数中值为奇数的个数。

数据范围

1n10181 \le n \le 10^{18}

题目链接

分析

这个题很水,但是有点意思。

首先根据 Lucas 定理,我们可以得知:

(nm)(nmod2mmod2)(n/2m/2)(mod2)(nmod2mmod2)(n/2mod2m/2mod2)(n/4m/4)(mod2)\begin{aligned}
\binom{n}{m} & \equiv \binom{n \bmod 2}{m \bmod 2}\cdot \binom{n \left. \right/ 2}{m \left. \right/ 2} \pmod 2 \
& \equiv \binom{n \bmod 2}{m \bmod 2} \cdot \binom{n \left. \right/ 2 \bmod 2}{m \left. \right/ 2 \bmod 2} \cdot \binom{n \left. \right/ 4}{m \left. \right/ 4} \pmod 2 \
\dots
\end{aligned}

也就是说,记 MiM_imm 二进制的第 ii 位,NiN_inn 二进制的第 ii 位,同时记 nn 的二进制有 kk 位,则:

(nm)i=1k(NiMi)(mod2)\binom{n}{m} \equiv \prod_{i = 1}^{k} \binom{N_i}{M_i} \pmod 2

显然,若要使得 (nm)1(mod2)\binom{n}{m} \equiv 1 \pmod 2,则对每一项都须有 (NiMi)1(mod2)\binom{N_i}{M_i} \equiv 1 \pmod 2

如果 Ni=0N_i = 0,那么当且仅当 Mi=0M_i = 0 时才会有 (NiMi)1(mod2)\binom{N_i}{M_i} \equiv 1 \pmod 2,而如果 Ni=1N_i = 1,那么不论 MiM_i 取何值都有 (NiMi)1(mod2)\binom{N_i}{M_i} \equiv 1 \pmod 2。因此,奇数的个数实际上就是所有 Ni=1N_i = 1 位上 MiM_i 的组合种数。记 nn 的二进制值为 11 的位数为 hh,那么由乘法原理答案显然就为 2h2^{h}

实现

完整参考代码

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/05/27/hduoj-4349/