花神的数论题

题目描述

设 \(\text{sum}(i)\) 表示 \(i\) 的二进制表示中 \(1\) 的个数。给出一个正整数 \(N\) ，花神要问你 \(\prod_{i=1}^{N}\text{sum}(i)\) ，也就是 \(\text{sum}(1)\sim\text{sum}(N)\) 的乘积。

数据范围

\(1\le N\le 10^{15}\)。

解法

首先我们要想到，把n表示成二进制位后，就可以从高位往低位做了，此时我们只需要处理单个的二进制位的\(sum(i)\)，然后算的时候再加上比他大的二进制位中1的个数即可。

所以现在问题转化成了，对于一个2的次幂，我们如何快速计算\(sum(i)\)。通过打表我们好像并没法一眼看出什么规律，于是我们直接从其原本意义开始想起。对于sum(8)，我们发现从1到7时前三位二进制，是从001(1)变成111(7)。想到组合数学，C(k,i)代表k位中有i个1的数量。而当二进制变为1000……的时候，其方案数也正好对应C(k,0)。所以对于n的每一个为1的二进制位，我们计算\(\prod_{i=1}^{k}{(i+res)}^{C(k,i)}\)。这个公式中，k表示这个二进制位数减一，res表示之前已经比该位大且为1的二进制位数。

出题人很好玩地把模数设为了10000007 ，痛wa两发。

然后看了题解，发现小粉兔的数位dp显然更优美。我们设dp[i]为1的个数为i的总次数，然后进行dp。第一维枚举二进制位，第二维枚举次数。转移式子为dp[i]+=dp[i-1]。转移完毕后如果当前二进制位的个数是j且该位为1，那么就dp[j-1]++。

我们来想一下其正确性。结合我们在上面提到的做法，不难理解转移后让dp[j-1]++，表示为还没加进来这个二进制位结尾。重点在于dp转移。我们会发现，第x位会在第倒数x次开始起到贡献，那么他的加入会使得每一个dp[i-1]背后的那个二进制加上他后变成dp[i]，并且只会从dp[j]开始起效果（因为轮到这个二进制位的时候，前面更大的1是不动的），并且只会起效果x次（这是比较对的，因为这一位最大也就只能转移到它原本就在的位置上）。

小粉土牛逼

代码实现

我自己的思路

const int mod=1e7+7;
ll binpow(ll a,ll b,ll c){
    ll ans=1;
    while(b){
        if(b&1)
        ans=(Int)ans*a%c;
        a=(Int)a*a%c;
        b>>=1;
    }
    return ans;
}
ll res[67][67]={0};
ll C(ll n,ll m){
    if(m==0 || m==n) return 1;
    if(res[n][m] != 0)return res[n][m];
    return res[n][m] = C(n-1,m)+ C(n-1,m-1);
}
void solve(){
    int n;cin>>n;
    vector<int>res;
    for(int j=62;j>=0;j--){
        if(n>>j&1)res.push_back(j);
    }
    ll ans=1;
    for(int i=0;i<res.size();i++){
        for(int j=0;j<=res[i];j++){
            ans=(ans*binpow(i+max(j,1ll),C(res[i],j),mod))%mod;
        }
    }
    cout<<ans<<"\n";

}

小粉兔的数位dp

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef __int128 Int;
const int mod=1e7+7;
ll binpow(ll a,ll b,ll c){
    ll ans=1;
    while(b){
        if(b&1)
        ans=(Int)ans*a%c;
        a=(Int)a*a%c;
        b>>=1;
    }
    return ans;
}
void solve(){
    int n;cin>>n;
    vector<int>dp(63);
    int idx=0;
    for(int j=62;j>=0;j--){
        for(int i=62;i>0;i--)
            dp[i]=dp[i]+dp[i-1];
        if(n>>j&1){dp[idx]++;idx++;}
    }
    dp[idx]++;
    ll ans=1;
    for(int i=1;i<63;i++){
        //cout<<i<<" "<<dp[i]<<endl;
        ans=ans*binpow(i,dp[i],mod)%mod;
    }
    cout<<ans<<"\n";
}
signed main(){
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    srand((unsigned)time(NULL));
    //int t;std::cin>>t;while(t--)
    solve();
}

唉，光理解别人的代码就费劲，那要怎么写出来呢？