题解 P3773 【[CTSC2017]吉夫特】

楼下说的这个结论估计很多像我一样的蒟蒻会懵掉吧。。。 那么为了帮助大家理解我就来证明一下这个结论吧 我们假设(n&m)==m,那么先假设这个结论是对的，看能不能找到反例推翻它。 1.当m的二进制最右位是1时： 这时n的二进制最右位肯定是1，所以((n-1)&(m-1))==m-1,可以递归证明C(n-1,m-1)是奇数； 又因为((n-1)&m)!=m,因为n-1的二进制最右位没有1了，所以可以递归证明 C(n-1,m)是偶数， 进而可以证明 C(n,m)是奇数。 2.m二进制最右位不是1时： 这样(m-1)的二进制最右端显然会有一排1(长度>=1)。 (1):如果此时n的二进制最右位的1和m是相同的位置，那么依然满足((n-1)&(m-1))==m-1。 有因为n的二进制最右位的1在n减去1之后被消去了，所以此时((n-1)&m)!=m，仍可证明C(n,m)是奇数。 (2):如果n二进制最右位的1在m二进制最右位1的右边，那么减去1后，m右端连续的变成1的序列会长于n，比如m=10100(2),n=10110(2),那么m-1=10011,n-1=10101,2^1这位m-1是1而n-1不是1，所以此时((n-1)&(m-1))!=m-1;又因为n减去1之后并不影响最右端1左边那些1，所以可以证明((n-1)&m)==m,这样又证明了C(n,m)是奇数。 代码楼上的就比较好了，我就不贴我的丑代码了hhh