Luogu

BZOJ

分析

显然$\mathrm{sum}$只有最多$50$种不同的取值。

枚举这个取值,然后用数位DP求出方案数,最后用快速幂乘起来。

至于怎么DP,我觉得代码应该很清楚了qwq

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=60;
const int MOD=10000007;

inline ll FastPow(ll a,ll b) {
    ll ans=1;
    for (;b;b>>=1,a=a*a%MOD)
        if (b&1) ans=ans*a%MOD;
    return ans;
}

int a[MAXN];
ll sum[MAXN];
ll f[MAXN][MAXN][MAXN][2];

inline ll dfs(int pos,int now,int sum,int limit) { //now是现在的1的个数,sum是要填的1的个数
    if (!pos) return now==sum;
    if (~f[pos][now][sum][limit]) return f[pos][now][sum][limit];
    int end=limit?a[pos]:1;
    ll ans=0;
    for (re int i=0;i<=end;++i)
        ans+=dfs(pos-1,now+(i==1),sum,limit&&i==end);
    return f[pos][now][sum][limit]=ans;
}

int main() {
    ll n=read(); int cnt=0;
    while (n) a[++cnt]=n&1,n>>=1;
    for (re int i=1;i<=50;++i) {
        memset(f,-1,sizeof(f));
        sum[i]=dfs(cnt,0,i,1);
    }
    ll ans=1;
    for (re int i=1;i<=50;++i)
        ans=ans*FastPow(i,sum[i])%MOD;
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 54 PM