蒟蒻不想取名字

BZOJ 3209 花神的数论题 数位DP+数论

//数位dp啊，用快速幂加速

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long int ll;

const int MAXN=60+5;

const ll mod=10000007;

ll n, Ans;

ll C[MAXN][MAXN];

int l,wei[MAXN];

void pre() {

    for (int i=0;i<=60;++i)

      C[i][0]=1;

    for(int i=1;i<=60;i++)

      for(int j=1;j<=i;++j)

        C[i][j]=C[i-1][j-1]+C[i-1][j];

}

ll Solve(int x) {

    ll sum=0;

    for (int i=l;i>=1;--i) {

      if(wei[i]==1){

        sum+=C[i-1][x];

        --x;

      }

      if(x<0) break;

    }

    return sum;

}

ll Pow(ll a, ll b){

    ll tot=1;

    a%=mod;

    while(b){

      if(b&1){

        tot*=a;

        tot%=mod;

      }

      b>>=1;a*=a;a%=mod;

    }

    return tot;

}

int main()

{

    pre();

    scanf("%lld",&n);

    ++n;//只能计算小于n的个数，所以要加1

    l=0;

    while(n){

      wei[++l]=n&1;

      n>>=1;

    }

    Ans=1ll;

    for(int i=1;i<=l;++i)

      Ans=Ans*Pow(i,Solve(i))%mod;

    printf("%lld\n",Ans);

    return 0;

}