代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 51;
const ll mod = 10000007;
ll n, dp[N][N], g[N], cnt;
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = a * ans % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll dfs(int p, int k, bool lim) {
    if (p < 0) {
        return (k == 0);
    }
    if (!lim && dp[p][k] != -1) return dp[p][k];
    ll ans = 0;
    for (int i = 0; i <= (lim ? ((n >> p) & 1) : 1); i++) {
        ans += dfs(p - 1, k - i, lim && (1 & (n >> p)) == i);
    }
    if (!lim) dp[p][k] = ans;
    return ans;
}
ll f(int s) {
    return dfs(50, s, 1);
}
ll ans = 1, w;
int main() {
    cin >> n;
    memset(dp, -1, sizeof(dp));
    for (ll i = 1; i <= 50; i++) {
        ans = (ans * qpow(i, f(i))) % mod;
    }
    cout << ans << endl;
}

提交记录

AC

WA&TLE