题目背景
众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
题目描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的：设 ext{sum}(i)sum(i) 表示 ii 的二进制表示中 11 的个数。给出一个正整数 NN ，花神要问你 prod_{i=1}^{N} ext{sum}(i)∏
i=1
N
sum(i) ，也就是 ext{sum}(1)sim ext{sum}(N)sum(1)∼sum(N) 的乘积。
输入格式
一个正整数 NN。
输出格式
一个数，答案模 1000000710000007 的值。
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const int mod=1e7+7;
typedef long long ll;
ll f[maxn][maxn];
int a[maxn],len;
ll L,R;
ll qpow (ll a,ll b) {
ll ans=1,base=a;
while (b) {
if (b&1) {
ans=ans*base%mod;
}
base=base*base%mod;
b>>=1;
}
return ans;
}
ll dfs (int pos,int st,int limit,int x) {
//x表示当前数位中1的个数
if (pos<=0) {
if (x)
return x;
else
return 1;
}
if (!limit&&f[pos][x]!=-1) return f[pos][x];
ll ans=1;
ll k=limit?a[pos]:1;
for (int i=0;i<=k;i++) {
if (st&&i==0) {
ans*=dfs(pos-1,st,limit&&i==k,x);
ans%=mod;
}
else {
if (i==0) {
ans*=dfs(pos-1,0,limit&&i==k,x);
ans%=mod;
}
else {
ans*=dfs(pos-1,0,limit&&i==k,x+1);
ans%=mod;
}
}
}
if (!limit&&!st) f[pos][x]=ans%mod;
return ans;
}
ll solve (ll x) {
len=0;
while (x) {
a[++len]=x%2;
x/=2;
}
memset(f,-1,sizeof(f));
return dfs(len,1,1,0);
}
int main () {
cin>>L;
cout<<solve(L);
}