首页 > 代码库 > HDU 4349 Xiao Ming's Hope

HDU 4349 Xiao Ming's Hope

很无语的一个题。

反正我后来看题解完全不是一个道上的。

要用什么组合数学的lucas定理。

表示自己就推了前面几个数然后找找规律。

C(n, m) 就是 组合n取m;


(m!(n-m!)/n!)

如果n==11 ;

C(11,0);C(11,1);C(11,2);C(11,3);C(11,4);C(11,5);

分别为

(1/1); (1 / 11) ; (11*10 / 2*1)  ;   (11*10*9 / 3*2*1); (11*10*9*8 / 4*3*2*1) ;  (11*10*9*8*7 / 5*4*3*2*1);


C(11,11);C(11,10);C(11,9);C(11,8);C(11,7);C(11,6);

这两个都是相等的。(参见排列组合)


若要 C(n,m)为奇数,必须  分子分母 约分后都是奇数。

发现如果纯模拟的肯定会超时的。

当时发现 当n==2^?  都是可以被除掉的,就只有 C(n,0);和 C(n,n) 都是 1,奇数。

而 n==(2^?)-1 的时候结果就是 2^n 。

然后推了前面几个数


1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

2,2,4,2,4,4,8,2,4,4  ,8  ,4  ,8  ,8  ,16,2 


巨像 树状数组。。。想到树状数组是取& 。

然后我就 转换 n 的二进制。发现有m个1 ,结果就是 2^m ;


于是终于AC。→ _ → 数学好伐。


#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
using namespace std;
int shift(int n)
{
    int cot=0;
    while(n)
    {
        if(n%2==1)cot++;
        n/=2;
    }
    return cot;
}
int main()
{
    int n,m;
    while(scanf("%d",&n)!=EOF)
    {
        m=shift(n);
        cout<<pow(2,m)<<endl;
    }
}