HNU 2015暑期新队员训练赛2 B Combination

先转化出求 Cnr中有多少奇数其实就是（n 的二进制数中 1 的个数为 k ，则这个奇数为 2 ^ k)

因为数很大，故要快速求出区间的奇数

然后求 0 – low-1 的奇数， 0- high 的奇数，相减既是结果

求 0 – N 中 Cnr 的奇数

通过上图可以快速求出 1 ---- (2^N)-1的个数，其他数则可以用迭代的方式求出来

（代码比赛写的有点残）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<map>

#include<set>

#include<vector>

#include<queue>

#include<stack>

//#include<bits/std c++.h>

using namespace std;

typedef __int64 LL;

typedef unsigned long long ULL;

const LL MOD = 1e7 + ;

const LL maxn = 1e6 + ;

ULL Num[] = {,,,};

LL SumL = , SumR = ;

ULL Pow(ULL a,ULL b)

{

    ULL ret = ;

    while(b)

    {

        if(b & ) ret = ret * a;

        a= a*a;

        b >>= ;

    }

    return ret;

}

/*ULL GetSum(ULL low, ULL high)

{

    ULL sum = high - low + 1;

        for(ULL E = low; E <= high; ++E)

        {

            for(ULL r = 1; r <= E; ++r)

                if((E & r) == r) sum++;

        }

        printf("%I64u\n",sum);

}*/

int main()

{

    ULL low, high;

    while(scanf("%I64u%I64u",&low,&high) != EOF && (high + low))

    {

        SumL = , SumR = ;

        //GetSum(low,high);

        ULL K = ;

        if(low == ) ;

        else {

            low --;

        if(low <= ) SumL = Num[low];

        else {while(low > )

        {

            ULL cnt = ;

            ULL tmp = low;  while(tmp) {cnt++, tmp >>= ;}

            SumL += Pow((ULL),cnt-) * Pow((ULL),K++);

            low -= Pow((ULL),cnt-);

        } SumL += Num[low] * Pow((ULL),K);

        }

        }

        ////////////

        if(high ==) ;

        else {

        if(high <= ) SumR = Num[high];

        else {K = ;

        while(high > )

        {

            ULL cnt = ;

            ULL tmp = high;  while(tmp) {cnt++, tmp >>= ;}

            SumR += Pow((ULL),cnt-) * Pow((ULL),K++);

            high -= Pow((ULL),cnt-);

        } SumR += Num[high] * Pow((ULL),K);

        }}

        cout << ULL(SumR-SumL) << endl;

    }

}

巴特西

HNU 2015暑期新队员训练赛2 B Combination

最新文章

热门文章