bzoj3209 花神的数论题

Description

背景
众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。
花神的题目是这样的
设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你
派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。

Input

一个正整数 N。

Output

一个数，答案模 10000007 的值。

预处理组合数

数位dp求出1~N的整数中二进制表示为i的数的个数

快速幂求总乘积

#include<cstdio>
#define M 10000007
typedef long long lint;
lint c[64][64],t[64],x,ans;
int mx=60;
lint power(lint x,lint n){
    if(n==1)return x;
    lint c=power(x,n>>1);
    if(n&1)return c*x%M*c%M;
    return c*c%M;
}
int main(){
    scanf("%lld",&x);
    while(!((x>>mx)&1))--mx;
    c[0][0]=1;
    for(int i=0;i<=60;i++)
        for(int j=0;j<=i;j++)
            c[i+1][j]+=c[i][j],c[i+1][j+1]+=c[i][j];
    for(int i=mx,c1=0;i>=0;i--){
        if((x>>i)&1){
            if(i)for(int j=1;j<=i;j++)t[j+c1]+=c[i][j];
            ++t[++c1];
        }
    }
    lint ans=1;
    for(int i=2;i<60;i++)
        if(t[i])ans=ans*power(i,t[i])%M;
    printf("%lld",ans);
    return 0;
}