HDU - 4349 - Xiao Ming's Hope（Lucas定理）

Xiao Ming likes counting numbers very much, especially he is fond of counting odd numbers. Maybe he thinks it is the best way to show he is alone without a girl friend. The day 2011.11.11 comes. Seeing classmates walking with their girl friends, he coundn’t help running into his classroom, and then opened his maths book preparing to count odd numbers. He looked at his book, then he found a question “C (n,0)+C (n,1)+C (n,2)+…+C (n,n)=?”. Of course, Xiao Ming knew the answer, but he didn’t care about that , What he wanted to know was that how many odd numbers there were? Then he began to count odd numbers. When n is equal to 1, C (1,0)=C (1,1)=1, there are 2 odd numbers. When n is equal to 2, C (2,0)=C (2,2)=1, there are 2 odd numbers… Suddenly, he found a girl was watching him counting odd numbers. In order to show his gifts on maths, he wrote several big numbers what n would be equal to, but he found it was impossible to finished his tasks, then he sent a piece of information to you, and wanted you a excellent programmer to help him, he really didn’t want to let her down. Can you help him?
Input
Each line contains a integer n(1<=n<=10 8)
Output
A single line with the number of odd numbers of C (n,0),C (n,1),C (n,2)…C (n,n).
Sample Input
1
2
11
Sample Output
2
2
8
题目链接
参考题解1
参考题解2

• 题目大意：题目大意：
  给你一个n，求C(n,1),C(n,2)……C(n,n)中奇数的个数
• 这个题目的话暴力就别想了，一定会TLE。看了题解说是要用到 lucas定理，然后就看题解看了很久，不明白，后来自己比着写了一下就明白了，所以有时候别总是看着，还是要动手。
  这个图片对于Lucas的解释再清楚不过了。取p = 2的时候，那么就只剩了四种情况：C(1,0)， C(0,1)， C(0,0)， C(1,1)，其中只有C(0,1) = 0，其余都是0。
  也就是，当C(n,i)中的n== 1时，不管i是多少，C(n,i)都是1，但n == 0时只有i ==0的时候才是1，所以我们把n和i都写成二进制，运用上述lucas定理。
  其实就是要看n写成二进制以后里面包含了多少个1，而不用关心0。 因为我们是统计出来二进制里面二进制的个数，每一个1都有两种情况，乘法法则，那么如果有x个1，那么i不同的情况就会有2^x种情况。我们之所以不用关心0，是因为对于0的时候，只有 i 的相应位置也是0的时候才可以，只有这一种情况，在我们对二进制中 1 对应种类计算过程中，考虑的是奇数的情况，那么也就是默认对应 n 二进制位是0的地方已经是0了，否则不成立也就不会出现这一种情况。
  AC代码：

#include <cstdio>
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int cnt = 0;
        while(n)
        {
            cnt += (n & 1);
            n >>= 1;
        }
        printf("%lld\n", 1LL << cnt);	//这里转化成long long类型，否则可能放不开
    }
    return 0;
}