目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

\(sum(i)\) 代表 \(i\) 的二进制数中 \(1\) 的个数，求 \(\prod_{i=1}^n sum(i)\)

State

\(mod = 10^7+7\)

\(1<=n<=10^{15}\)

Input

3

Output

2

Solution

因为需要知道 \(sum(1), sum(2), ....sum(n)\) 的值，\(O(n)\) 的方法肯定是不行的，所以需要另辟蹊径，如果可以计算出包含 \(i\) 个 \(1\) 的 \(sum()\) 的个数，利用快速幂可以解决这个问题

剩下的还是老样子，\(dp[pos][sum]\) 表示到达 \(pos\) 位置处，已经有 \(sum\) 个 \(1\) 时拥有 \(sum()\) 的个数，但是这样还不够好，因为需要多次初始化，不放在加一维表示所需要 \(1\) 的个数

Code

ll mod = 1e7 + 7;

    ll n, m, _;
    int i, j, k;
    int a[55];
    int tot;
    ll dp[55][55][55];

ll pow_mod(ll a, ll x)
{
    ll ans = 1;
    while(x){
        if(x & 1) ans = ans * a % mod;
        a = (a * a) % mod;
        x >>= 1;
    }
    return ans;
}

ll reap(ll &x)
{
    x %= mod;
    x += mod;
    x %= mod;
    return x;
}

ll dfs(int pos, int sum, bool top, int all)
{
    if(! pos) return (sum == all);
    if(! top && dp[pos][sum][all] != -1) return dp[pos][sum][all];
    int up = 1; ll ans = 0;
    if(top) up = a[pos];
    for(int i = 0; i <=  up; i ++){
        ans += dfs(pos - 1, sum + (i == 1), top & (i == up), all);
    }
    if(!top) dp[pos][sum][all] = ans;
    return ans;
}

ll solve(ll x)
{
    tot = 0;
    while(x) a[++ tot] = x & 1, x >>= 1;
    ll bit[55] = {0}, ans = 1;
    ms(dp, -1);
    for(int i = 1; i <= 50;i ++){
        bit[i] = dfs(tot, 0, 1, i);
        ans *= pow_mod(i, bit[i]);
        reap(ans);
    }
    return ans;
}

signed main()
{
    //IOS;
    while(~ sll(n)){
        pll(solve(n));
    }
    return 0;
}