【题解】洛谷P1869愚蠢的组合数

题目

洛谷P1869愚蠢的组合数

题解

由于n较大,考虑使用卢卡斯定理,C(n,m) mod 2=0/1,即可判断奇偶性。C(0,0)=1,C(1,1)=1,C(0,1)=0,C(1,0)=1。

优化:考虑lucas定理中的两个操作(n/p和n mod p),如果反复执行这样的操作,直至n<p,那么这个过程相当于将n,m进行p进制分解,然后将p进制下的每一位分别计算组合数,并相乘。此题p=2,就是二进制分解。如果出现某一位,m为1,n为0,则结果为0,否则为1。

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月30日 上午10:37

【小白解析】
此题的优化初看较难理解,实际上是对lucas()中的递归进行剖析。
如博主在优化部分所说:

考虑lucas定理中的两个操作(n/p和n mod p),如果反复执行这样的操作,直至n<p,那么这个过程相当于将n,m进行p进制分解,然后将p进制下的每一位分别计算组合数,并相乘。

再具体查看第一段中,?表达式后的递归部分:

lucas(n/2,m/2)*lucas(n%2,m%2)%2

假设n和m都大于2。因为任何x%2都小于2,满足?表达式的判断条件,故可以尝试用数组表示不同迭代中这一部分表达式的值:
迭代1:lucas(n/2,m/2)*c[n%2][m%2]
迭代2:lucas(n/4,m/4)*c[(n/2)%2][(m/2)%2]*c[n%2][m%2]
……
迭代k:lucas(n/2^k,m/2^k)*c[(n/2^(k-1))%2][(m/2^(k-1))%2]*c[(n/2^(k-2))%2][(m/2^(k-2))%2]*……*c[(n/2)%2][(m/2)%2]*c[(n%2][(m%2]
到了最终的log2(n)迭代,该表达式的值则可以理解成所有c[(n/2^k)%2][(m/2^k)%2]的乘积(k从0开始)。而所有(n/2^k)%2与(m/2^k)%2,则各表示了n和m在二进制表达式下,第k-1位的值。因此,lucas表达式的结果即为“对m和n二进制表达式下,相同位数的值nk与mk取组合数c[nk][mk],并将所有c[nk][mk]相乘”。
而本题需要的所有组合数中,只有c[0][1]==0(即nk==0而mk==1时)。只要乘积中出现一个0,乘积整体必为0。此处只需要考察二进制表示下,是否有n的某一位为0而m的相应位为1的情况,即(n&m)==m。
*建议把“奇偶性”定义成“逆序对数量”来增加难度。