BZOJ-3209: 花神的数论题

Description

设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。N≤10^15，输出一个数，为答案模 10000007 的值。

数位DP。dp[i][j]表示i位01串j个1的方案数。枚举1的位数求方案快速幂即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;//2^50>10^15
typedef long long ll;
const ll mod=10000007;
ll n,dp[60][60];//dp[i][j]:i 位二进制 j 个 1 的方案数
int mx;
void initialize()
{
    dp[0][0]=dp[1][1]=dp[1][0]=1; int i;
    for(i=2;(n>>i);++i)
    {
        dp[i][0]=1;
        for(int j=1;j<=i;++j)
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
    }
    mx=i-1;
}
ll getans(int j)
{
    ll re=0;
    for(int i=mx;i>=0;--i) if((n>>i)&1)
    {
        re+=dp[i][j];
        j--;
        if(j<0) break;
    }
    return re;
}
ll Pow(ll x,ll y)
{
    ll re=1;
    while(y)
    {
        if(y&1) re=re*x%mod;
        x=x*x%mod; y>>=1;
    }
    return re;
}
int main()
{
    scanf("%lld",&n); ++n;
    initialize();
    ll ans=1;
    for(int i=1;i<=mx;++i) ans=ans*Pow(i,getans(i))%mod;
    printf("%lld",ans);
    return 0;
}