pythonTip 74 C(n,k)

题目描述： 求组合数 C ( n , k) 的奇偶性. 给你n和k(1<=n<=10^9,0<=k<=n),若其为奇数，则输出1，否则输出0. 如n=2,k=0,则输出1. 因为C(2,0)=1,为奇数。

示例： 输入： n = 2 k = 0 输出： 1

分析:

首先来看卡 C(n, k) 是如何计算的。

C(n,k) = n! / (k! * (n-k)! )

所以： C(n, k) = C(n, n-k)

对于 C(9, 4) = 9! / (4! * 5!) = 9 * 8 * 7 * 6 / (1*2*3*4)

我们可以化简最后就变成了 3*2*7*3

让我们来小小的分析一下，这是一个数学问题。有4点小性质

1. 当 k == 0 或 n == k 时。结果等于1
2. C(n, k) = C(n, n-k)
3. 当化简以后，如果出现一个 偶数，那么结果就为偶数。 偶数 * 任何数 = 偶数
4. 如果化简后，全是奇数，那么结果就为奇数。 奇数*奇数 = 奇数

基于上面的一个简单分析，首先我们根据 C(n, k) = C(n, n-k), 将，k 的值减小。然后判断是否满足第一点，如果满足第一点，那么就可以直接给出答案。如果不是，我们再来小小的分析一下。

我们最后关注的是，是否有偶数的出现，偶数是啥？就是2的倍数，那么我们最后可以统计 前面的分子里面包含了多少个 2。 例如 2， 6， 14 就是只包含了 1 个 2， 例如 4 就是包含了两个2， 8 就是包含了3个2。 然后我们再统计一下，分母里面包含2的个数。

最后我们对比一下分子和分母中2 的个数，这样就可以判断最后结果的奇偶性了。

当然，我的代码最后是没有根据第二点做一个转换的，问题不大。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

res = 0
if k == 0 or n == k:
    res = 1
else:
    nn = 0
    while n:
        nn += (n // 2)
        n //= 2
    
    nk = 0
    while k:
        nk += (k // 2)
        k //= 2
    
    if nn > nk:
        res = 0
    else:
        res = 1
print(res)