题目链接

题目描述

$O(1)$ 判断 $C(n,m)$ 的奇偶性

简要做法

Lucas 定理

$C(n,m) \equiv C(n \bmod 2, m \bmod 2) * C(n / 2, m / 2) \quad (\bmod 2 \ )$

如果是奇数

$C(n \bmod 2, m \bmod 2) \equiv C(n / 2, m / 2) \equiv 1 \quad (\bmod 2 \ )$

左边那东西就是要求 $n \bmod 2 = 1$

右边那东西看起来不太显然，其实就是 $C(n » 1, m » 1) \equiv 1 \quad (\bmod 2 \ )$

递归下去，结合左边那东西看就是二进制下 $n$ 的前 $\log_2m$ 位都得是 1

也就是说当且仅当 n & m = m 且 n != 0 时，C(n,m) 为奇数

参考代码

#include <stdio.h>

int n;

int main()
{
    while (~scanf("%d", &n))
    {
        int k = 0, ans = 1;
        while (n)
            k += n % 2, n /= 2;
        for (int i = 1; i <= k; i++)
            ans *= 2;
        printf("%d\n", ans);
    }
    return 0;
}