DP，数论————洛谷P4317 花神的数论题（求1~n二进制中1的个数和）

玄学代码（是洛谷题解里的一位dalao小粉兔写的）

//数位DP(二进制)计算出f[i]为恰好有i个的方案数。
//答案为∏(i^f[i]),快速幂解决。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=10000007;
ll n,ans=1;
ll c,f[50];
ll qpow(ll b,ll e){
    ll a=1;
    for(;e;b=b*b%mod,e>>=1)
        e&1?a=a*b%mod:0;
    return a;
}

int main(){
    scanf("%lld",&n);
    for(int j=49;~j;--j){
        for(int i=49;i;--i)
            f[i]+=f[i-1];
        if(n>>j&1)++f[c++];
    }++f[c];
    for(int i=1;i<=49;++i)
        ans=ans*qpow(i,f[i])%mod;
    printf("%lld",ans);
    return 0;
}

下面是另一位dalaoStyx写的简单易懂的题解

代码如下

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 10000007
using namespace std;

long long ans=1,n,k,cnt,dp[110][110];

long long kasumi(long long a,long long b)
{
    long long tmp=1;
    while(b)
    {
        if(b&1) tmp=(tmp%mod)*a%mod;
        a=(a%mod)*a%mod;
        b>>=1;
    }
    return tmp%mod;
}

int main()
{
    scanf("%lld",&n);
    for(int i=1; i<=60; i++)
    {
        dp[i][1]=1;
    }
    for(int i=1; i<=60; i++)
    {
        dp[i][i]=1;
    }
    for(int i=2; i<=60; i++)
    {
        for(int j=2; j<i; j++)
        {
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
        }
    }
    for(k=1; k<=n; k<<=1)
    {
        n-=k;
        cnt++;
        for(int j=1; j<=cnt; j++)
        {
            ans=(ans%mod)*kasumi(j,dp[cnt][j])%mod;
            ans%=mod;
        }
    }
    cnt=0;
    for(int i=60;i>=0;i--)
    {
        if((1ll<<i)<=n)
        {
            for(int j=1;j<=i+1;j++)
            {
                ans=(ans%mod)*kasumi(j+cnt,dp[i+1][j]);
                ans%=mod;
            }
            cnt++;
            n-=(1ll<<i);
        }
    }
    printf("%lld
",ans);
}

至于为什么不用扩展欧拉定理降幂，那是因为杨辉三角在总和等于1e15的时候 ，每一个数肯定不会爆longlong