HDU2502 月之数组合数

月之数

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2744 Accepted Submission(s): 1585

Problem Description

当寒月还在读大一的时候，他在一本武林秘籍中（据后来考证，估计是计算机基础，狂汗-ing），发现了神奇的二进制数。
如果一个正整数m表示成二进制，它的位数为n（不包含前导0），寒月称它为一个n二进制数。所有的n二进制数中，1的总个数被称为n对应的月之数。
例如，3二进制数总共有4个，分别是4（100）、5（101）、6（110）、7（111），他们中1的个数一共是1＋2＋2＋3=8，所以3对应的月之数就是8。

Input

给你一个整数T，表示输入数据的组数，接下来有T行，每行包含一个正整数 n（1<=n<=20）。

Output

对于每个n ，在一行内输出n对应的月之数。

Sample Input

Sample Output

1
3
8

　　该题题义简单，是求一个二进制数的区间内，1的个数，不知到有木有更好的办法，写这道题时想到的就是一个组合问题。

　　比如要求一个4二进制数的月之数是多少，由于第一位必须为1，所以有多少个3位的二进制数，就有多少个高位1，后面的就是从N-1个里面选一个，两个...... 这样的组合数，在具体计算过程中还要考虑奇偶性。

　　代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 using namespace std;
 5 
 6 long long mix( long long n, long long m )
 7 {
 8     long long res = 1;
 9     for( long long i = 0; i < m; ++i )
10     { // 一直用这个学来的方法来防止溢出
11         res *= ( n - i );
12         res /= ( i + 1 );
13     }
14     return res;
15 }
16 
17 int main()
18 {
19     int T;
20     scanf( "%d", &T );
21     while( T-- )
22     {
23         long long N, ans = 1;
24         scanf( "%I64d", &N );
25         for( long long i = 1; i <= N - 1; ++i )
26         {
27             ans <<= 1;
28         }    
29         if( ! ( N & 1 ) )
30         {
31             int lim = N / 2 - 1;
32             for( long long i = 1; i <= lim; ++i )
33             {
34                 ans += ( N - 1 ) * mix( N - 1, i );
35             }
36             ans += ( N - 1 );
37         }
38         else
39         {
40             int lim = ( N - 1 ) / 2;
41             for( long long i = 1; i < lim; ++i )
42             {
43                 ans += ( N - 1 ) * mix( N - 1, i );
44             } 
45             ans += ( N - 1 ) / 2 * mix( N - 1, ( N - 1 ) / 2 ); 
46             ans += ( N - 1 ); 
47         }
48         printf( "%I64d\n", ans );
49     }
50     return 0;
51 }

　　突然想到用移位判定奇偶来统计1的个数，现在就去试试看。

　　上面的这种方法也能过，代码量下来了，但是速度慢了 78MS，前面的是0MS。代码如下：

 1 #include <cstring>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int T;
 9     scanf( "%d", &T );
10     while( T-- )
11     {
12         int N, beg = 1, end = 1, ans = 0;
13         scanf( "%d", &N );
14         for( int i = 1; i < N; ++i )
15             beg <<= 1, end <<= 1;
16         end <<= 1, end -= 1;
17         for( int i = beg; i <= end; ++i )
18         {
19             int t = i;
20             while( t > 0 )
21             {
22                 if( t & 1 )
23                     ++ans;
24                 t >>= 1;
25             }
26         }
27         printf( "%d\n", ans );
28     }
29     return 0;
30 }

　　还有一种递推解法，个人觉得很好很强大。代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 using namespace std;
 5 
 6 int ans[22], base = 1;
 7 
 8 int main()
 9 {
10     ans[1] = 1;
11     for( int i = 2; i <= 20; ++i )
12     {
13         ans[i] = 2 * ans[i-1] + base;
14         base <<= 1;
15     }
16     int T;
17     scanf( "%d", &T );
18     while( T-- )
19     {
20         int N;
21         scanf( "%d", &N );
22         printf( "%d\n", ans[N] );
23     }
24     return 0;
25 }

HDU2502 月之数 组合数

月之数

HDU2502 月之数组合数