• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

组合数的奇偶性

开发技术 开发技术 3天前 7次浏览

组合数可以表示为

[C^m_n = frac{n!}{m!(n-m)!}
]

假设(n!,m!,(n-m)!)含因子(2)的个数分别为(A,B,C)
则当(A=B+C)时,(C^m_n)为奇数

那么如何求出(n!)的因子个数呢?
对于一个质数(p)
它的倍数(k*p^i)含因子(p)的个数为即为(i(k=1,2,3…))
于是只要求出(n!)中所有的(k*p^i)即可,
(n!)含因子(p)的个数为

[lfloor frac{n}{p} + frac{n}{p^2} + frac{n}{p^3} + frac{n}{p^4} + … rfloor
]

所以(n!)含因子(2)的个数为

[f(n) = lfloor frac{n}{2} + frac{n}{2^2} + frac{n}{2^3} + frac{n}{2^4} + … rfloor
]

其中,可以将(n)表示为二进制拆分的形式:

[n = (a_1*2^0)+ (a_2*2^1)+ (a_3*2^2)+ (a_4*2^3)+…
]

(f(n))就可以表示成

[f(n) = sum limits_{j=1}^{k} frac{(a_1*2^0)+(a_2*2^1)+…+ (a_k*2^{k-1})}{2^j}
]

将式子简化

[= sum limits_{j=1}^{k} frac{(a_{j-1}*2^j)+…+ (a_k*2^{k-1})}{2^j}
]

[= sum limits_{j=1}^{k} sum limits_{i=j+1}^{k} frac{a_{i}*2^{i-1}}{2^j}
]

[= sumlimits_{i=1}^{k} a_i sumlimits_{j=1}^{i-1} frac{2^{i-1}}{2^j}
]

[= sumlimits_{i=1}^{k} a_i sumlimits_{j=0}^{i-2} 2^j
]

[= sumlimits_{i=1}^{k} a_i * (2^{i-1} – 1)
]

[= sumlimits_{i=1}^{k} a_i * 2^{i-1} – sumlimits_{i=1}^{k} a_i
]

[= n – sumlimits_{i=1}^{k} a_i
]

观察这个式子,可以发现

[sumlimits_{i=1}^{k} a_i = n在二进制下1的个数
]

(n,m,(n-m))在二进制下(1)的数目分别为(a,b,c)
要满足(A=B+C),则:

[n−a=m−b+(n−m)−c
]

[a=b+c
]

要满足这个条件则有

[(n&m) == m
]


程序员灯塔
转载请注明原文链接:组合数的奇偶性
喜欢 (0)