P4317 花神的数论题

题解

关于二进制的数位DP

dfs 套路

问题在于哪里，在于存二进制的时候数组只开了20，现实是输入的数据可能会达到比二十长，此时就拿了个错误的数据在计算不WA才怪数组开大一点没关系啊只要不RE就好了

问题是求1~n中每个数二进制表示中1的乘积

其实问题也就转化成：枚举1的个数k，然后统计有多少个数字含有k个1

k=log₂n

ans= ∏ k ^sum(k)

k=1

我们可以先把 n 二进制拆分，然后枚举 1 的个数，比如二进制表示中有 1 个 1 的数字有几个，2个的有几个，....，然后快速幂乘起来，二进制表示中有1个1的就不用算了，乘了还是原数

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>

using namespace std;

typedef long long ll;

inline ll read()
{
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0'||ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

const ll mod=1e7+7;
ll n;
ll x[80],len=0;
ll dp[80][80][80][20];

void cl(ll n)
{
    while(n)
    {
        x[++len]=n%2;
        n/=2;
    }
/*    printf("%lld
",len);
    for(ll i=len;i>0;i--)
      printf("%lld ",x[i]);
    printf("
");*/
}

ll dfs(ll pos,ll already,ll need,bool limit)
//当前填到了第几位，已经有几个1了，需要几个1，是否顶上界
{
    if(pos<=0) return already==need;
    if(!limit&&dp[pos][already][need][limit]!=-1) return dp[pos][already][need][limit];
    ll ans= 0;
    ll up=limit?x[pos]:1;
    for(ll i=0;i<=up;i++)
      ans+=dfs(pos-1,already+(i==1),need,limit&&(i==up));
    if(!limit) dp[pos][already][need][limit]=ans;
    return ans;
}

ll ksm(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b%2==1) res=res*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return res;
}

int main()
{
    n=read();
    cl(n);
    memset(dp,-1,sizeof(dp));
    ll ans=1;
    for(ll i=len;i>=2;i--)
      ans=ans*ksm(i,dfs(len,0,i,1))%mod;
    printf("%lld
",ans);
    return 0;
}

附上听课笔记：

◦ 这题的关键就是发现一的个数的情况比较少可以枚举再转化为另一种情
况计算其实，这题本质就是转化一下，注意在模型难以建立的情况下，
通过转化，可以将题目简化