题目链接：
花神的数论题 – 洛谷
分析：就是对于1~n中的每个数，把他二进制中含有的1的个位乘起来即可。n是小于1e15的，所以n的二进制位也不会超过70，所以说1~n中的所有数含有1的个数是1~70，所以对于k属于区间[1,70]，
我们可以用数位DP求出二进制数中含有1的个数为k的数的数目sum，这样k的贡献就是sum个k连乘，也就是k的sum次方，这样我们枚举每一个二进制表示中可能含有的1的个数就可以得到最终的贡献
，而求每一个二进制表示中可能含有的1的个数就是一个基本的数位DP，我们只需要在数位DP过程中记录当前已经出现多少个1以及最后需要出现多少个1即可。
但是需要注意两个问题：
（1）对于满足同一个条件的多组询问，则我们上次记忆化的f数组依旧能用于下一次，所以f数组只需要初始化一次，而本题每次数位DP满足的条件都不一样（二进制表示中含有的1的个数不同）,所以我们每次都需要重新初始化f数组
（2）因为答案涉及到取模，但是需要注意的是我们仅仅能在加法减法或者乘法过程中随意取模，但是我们不能在求指数的过程中取模，否则会出现错误
这就是本道题目的思路了，下面是代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int N=70,mod=10000007;
ll f[N][N];//表示后i位可以任选且前i位含有j个1的个数
ll a[N];
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a%mod*a%mod;
b>>=1;
}
return ans;
}
ll dp(int pos,int cnt,int limit,int t)//因为求的是指数，所以在求DP过程中不能模mod
{
if(!pos) return cnt==t;
if(cnt>t) return 0;//剪枝
if(!limit&&f[pos][cnt]!=-1) return f[pos][cnt];
ll ans=0;
int up=limit?a[pos]:1;
for(int i=0;i<=up;i++)
ans+=dp(pos-1,cnt+(i==1),limit&&(i==up),t);
if(!limit) f[pos][cnt]=ans;
return ans;
}
ll solve(ll x)
{
ll ans=1;
int pos=0;
while(x)
{
a[++pos]=x%2;
x/=2;
}
for(int i=1;i<=pos;i++)
{
memset(f,-1,sizeof f);//因为我们每次求的满足条件不一样，所以每次都需要初始化
ans=ans*(qpow(i,dp(pos,0,1,i)))%mod;
}
return ans;
}
int main()
{
ll n;
cin>>n;
cout<<solve(n);
return 0;
}
当然这道题目也可以不用枚举k，可以直接求出来，我们
原来f[i][j]表示后i位可以任选且前i位含有j个1的个数,
这样我们最后搜索到的结果就是含有k个1的数的个数，然后我们在函数外面进行求解k的贡献，当然我们可以更改f数组的含义来直接求出总贡献，就是
令f[i][j]表示后i位可以任选且前i位含有j个1的贡献
,然后我们在返回的时候就是返回任选的贡献了，而且贡献之间的关系是满足乘法原理的，这样求解贡献的话就不需要递归调用很多次函数从而减少代码运行时间。
下面附上代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int N=70,mod=10000007;
ll f[N][N];//f[i][j]表示后i位可以任选且前i位含有j个1的贡献
ll a[N];
ll dp(int pos,int cnt,int limit)
{
if(!pos) return cnt?cnt:1;
if(!limit&&f[pos][cnt]!=-1) return f[pos][cnt];
ll ans=1;
int up=limit?a[pos]:1;
for(int i=0;i<=up;i++)
ans=ans*dp(pos-1,cnt+(i==1),limit&&(i==up))%mod;
if(!limit) f[pos][cnt]=ans;
return ans;
}
ll solve(ll x)
{
memset(f,-1,sizeof f);
ll ans=1;
int pos=0;
while(x)
{
a[++pos]=x%2;
x/=2;
}
return dp(pos,0,1)%mod;
}
int main()
{
ll n;
cin>>n;
cout<<solve(n);
return 0;
}