题意简述
设( ext{sum}(i))为(i)的二进制中(1)的个数，求
[prod_{i = 1} ^ n ext{sum}(i)
]
(n le 10 ^ {15})。
简单口胡
考虑对每个数求( ext{sum}(i))肯定是不行的，只能考虑将思维转到求“有多少数的( ext{sum}(i) = x)，然后对(x)进行操作，因为( ext{sum}(i))的最大值也就(50)左右，大大降低复杂度。
具体地，考虑求出( ext{S}_i = sum_{k = 1} ^ n {[ ext{sum}(k) = i]})，答案即为
[prod_{i = 1} ^ {log{n}} i ^ { ext{S}_i}
]
考虑数位( ext{dp})，设( ext{dfs}(n,cnt,now))为当前在第(now)位，当前有(cnt)位为(1)，目标要求(n)为为(1)的答案。
记忆化搜索，记得要反着搜。
别忘了必要的剪枝。
# include <bits/stdc++.h>
using namespace std;
long long x;
const long long mod = 10000007;
const int M = 52;
long long dp[M][M][M];
int N;
int a[M];
long long q[M];
long long dfs(int n,int cnt,int now,bool op)
{
// printf("n = %d,cnt = %d,now = %d,op = %d
",n,cnt,now,op);
if(now == -1) return cnt == n;
if(cnt + now + 1 < n) return dp[n][cnt][now] = 0;
if(!op && dp[n][cnt][now] != -1) return dp[n][cnt][now];
int limit = (op == 1) ? a[now] : 1;
long long ans = 0;
for(int i = 0; i <= limit; i++)
{
ans = ans + dfs(n,cnt + (1 == i),now - 1,op && i == limit);
}
if(!op) dp[n][cnt][now] = ans;
return ans;
}
long long qmulti(long long x,long long p)
{
long long ans = 1;
while(p)
{
if(p & 1)
{
ans = (ans * x) % mod;
}
p >>= 1;
x = (x * x) % mod;
}
return ans;
}
void solve(void)
{
N = log2(x);
for(int i = N; i >= 0; i--)
{
if((x >> i) & 1) a[i] = 1;
}
// printf("N = %d
",N);
// printf("Yes:chaifen
");
N++;
for(int i = N; i >= 1; i--)
{
memset(dp,-1,sizeof(dp));
// printf("i = %d
",i);
q[i] = dfs(i,0,N - 1,1);
// printf("q[%d] = %lld
",i,q[i]);
}
// printf("Yes:q
");
long long ans = 1;
for(int i = N; i >= 1; i--)
{
ans = (ans * qmulti(i,q[i]))% mod;
}
printf("%lld
",ans);
}
int main(void)
{
scanf("%lld",&x);
solve();
return 0;
}