[P4317 花神的数论题]题解

P4317 花神的数论题【数位DP】

题目描述

最开始其实没有什么想法
第一次遇见数位dp求相乘的题
想就按照常规做法来做，但不知道如何去处理*
于是写了一个错误的代码

//当前枚举到第id位，前面的1的个数为sum，是否达到上限limit
ll dfs(int id,int sum,int limit){
  //1.出口
  if(id==0) return 1ll*sum;
  if(dp[id][sum][limit]!=-1) return dp[id][sum][limit];
  //2.能做的事情 
  int bound=limit?a[id]:1;
  ll res=1;
  for(int i=(id==1?1:0);i<=bound;i++)
    res=1ll*res*dfs(id-1,sum+(i==1),limit&&i==bound)%mod;
  return dp[id][sum][limit]=res%mod;
} 

ll solve(ll x){
  len=0;
  memset(dp,-1,sizeof(dp));
  while(x){
  	a[++len]=x%2;
  	x/=2;
  }
  return dfs(len,0,1);
}

很明显我知道是错的
但又不太清楚是哪里错了
应该是在乘法的记忆化上面出了一些问题
提交上去也只有10分
……
[看了看题解]
……
我们不妨换一个角度来思考
它要求每一个数的\(sum\)乘积
由于\(n \leq 10^{15}\)
所以其实\(sum\)是有限的
也就是\(0 \to 50\)中的数
所以我们可以把每一个\(sum\)的个数都求出来再用快速幂乘起来
这样就是一个很典型的数位dp了
但对于每一个不同的\(sum\)
我们都要用一次\(dfs\)去求，不然是无法用上记忆化
会导致\(TLE\)

//当前枚举到第id位，前面1的数量为sum，正在统计num的个数，是否达到上限limit
//统计cnt[sum]，sum出现的次数 
ll dfs(int id,int sum,int num,int limit){
  //1.出口
  if(id==0) return sum==num;
  if(dp[id][sum][num][limit]!=-1) return dp[id][sum][num][limit];
  //2.能做的事情 
  int bound=limit?a[id]:1;
  ll res=0;
  for(int i=0;i<=bound;i++)
    res+=dfs(id-1,sum+(i==1),num,limit&&i==bound); 
  return dp[id][sum][num][limit]=res;
}

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

int main(){
  /*2023.4.15 hewanying P4317 花神的数论题 数位DP*/ 
  scanf("%lld",&n);
  memset(dp,-1,sizeof(dp));
  len=0;
  while(n){
  	a[++len]=n%2;
  	n/=2;
  }
  ans=1ll;
  for(int i=1;i<=len;i++) 
    ans=ans*quickpow(1ll*i,dfs(len,0,i,1))%mod;
  printf("%lld\n",ans);
  return 0;
}

总结

对于这种要转个弯的数位dp题，我们的目的还是要把乘积转化成加法
考虑答案的构成，把相同的sum放在一块
这样就可以把题目中的\(\Pi\)转化成\(\Sigma\)
便可以用数位dp解决了