BZOJ 3209

Description:

令函数 表示 在二进制表示下 的个数。求 取模的答案。



Solution:

很简单的一道数位 题,首先递推出组合数,然后逐位 即可,由于比较简单就不具体解释了。

细节:快速幂的时候不要对指数取模,如果你实在想要取模也可以,把指数对 取模。但是 不是质数,事实上


Code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

long long N;
const long long Mod=10000007;
int to2[100]={0};
long long C[70][70]={{0}};

long long power(long long a,long long k)
{
    long long o=1;
    for(;k>0;k>>=1)
    {
        if(k&1) o=o*a%Mod;
        a=a*a%Mod;
    }
    return o;
}

int main()
{
    cin>>N;
    int tp=0;
    for(;N>0;N>>=1)
        to2[++tp]=(N&1);
    int count=0;
    C[0][0]=1;
    for(int i=1;i<=65;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=65;j++)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    long long ans=1;
    for(;tp>0;tp--)
    {
        if(to2[tp]==1)
        {
            for(int i=(count==0);i<=tp-1;i++)
                ans=ans*power(count+i,C[tp-1][i])%Mod;
        }
        count+=(to2[tp]==1);
    }
    cout<<ans*count%Mod<<endl;
    return 0;
}