洛谷 P4317 花神的数论题（数位DP || 快速幂）

题目链接：https://www.luogu.com.cn/problem/P4317

与数字计数像极了，并且更容易一些，只是数据范围大一些，思路是完全一样的，并且前导0并没有影响：

找出二进制下有1个1的有多少数，2个1，3个1.....用&来拆分即可，最后用快速幂进行乘法运算进行一下优化。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 const ll mod=10000007;
 9 ll dp[60][60][60];
10 int a[60];
11 ll ksm(ll x,ll y,ll p){
12     ll ans=1;
13     while(y){
14         if(y&1) ans=ans*x%p;
15         x=x*x%p;
16         y>>=1;
17     }
18     return ans;
19 }
20 ll DFS(int pos,int limit,int now,int cnt){
21     if(pos==0) return now==cnt;
22     if(!limit&&dp[pos][now][cnt]!=-1) return dp[pos][now][cnt];
23     int up=limit?a[pos]:1;
24     ll ans=0;
25     for(int i=0;i<=up;i++) ans+=DFS(pos-1,limit&&i==a[pos],now+i,cnt);
26     if(!limit) dp[pos][now][cnt]=ans;
27     return ans;
28 }
29 ll solve(ll x){
30     int len=0;
31     ll sum=1;
32     memset(dp,-1,sizeof(dp));
33     while(x){
34         a[++len]=x&1;
35         x>>=1;
36     }
37     for(int i=1;i<=len;i++){
38         ll ans=DFS(len,1,0,i);
39         sum=sum*ksm(i,ans,mod)%mod;
40     }
41     return sum;
42 }
43 int main(){
44     ll n;
45     scanf("%lld",&n);
46     printf("%lld",solve(n));
47     return 0;
48 }

AC代码