題意簡介

沒什么好說，就是讓你求出 1 ~ n 之間每個數轉化為二進制后 '1' 的個數，然后乘起來輸出積

?

題目分析

emmmm.... 兩種解法（同是 $O(\log^2 N)$ 的算法，組合數效率完爆 數位dp，當然是我自己的數位dp）。

組合數直接艸。（數據范圍8e9 能過，其實這個東西你搞一搞 __int128 什么的再找個大質數也許也能過去啦）（好吧這個直接暴力預處理組合數的數組就好了）

老老實實數位dp。（可以AC）

于是翻車了...這么久

?

算法實現

1. 組合數?

組合數非常好做，只需要想想第 i 位為 1 的位上后面那一堆數字里面挑出 j 個數的方案就好了，注意加上 cnt ，然后最后快速冪累加一下答案，分分鐘搞定

然后這里用了逆元處理組合數要預處理的階乘，如果你還不會線性求逆元的話可以點這里

當然這里用逆元...就是作死...我們完全可以預處理出 50 * 50 的楊輝三角數組，存好組合數直接用

?

2.數位dp

...不就是枚舉 1 的個數然后記憶化深搜么？hem...聽起來完全沒有組合數高級

?

?

?

代碼實現

1.組合數

1 //by Judge 2 #include<iostream> 3 #include<cstdio> 4 #define ll long long 5 using namespace std; 6 const int M=55; 7 const ll mod=1e7+7; 8 ll n,len,cnt,ans=1; 9 ll C[M][M],d[M],num[M]; 10 inline void prep(){ //預處理組合數模板？ 11 for(int i=0;i<=50;++i) C[i][0]=1; 12 for(int i=1,j;i<=50;++i) for(j=1;j<=50;++j) 13 C[i][j]=C[i-1][j]+C[i-1][j-1]; 14 } 15 inline ll quick_pow(ll x,ll p,ll ans=1){ //快速冪模板？ 16 while(p){ 17 if(p&1) ans=ans*x%mod; 18 x=x*x%mod, p>>=1; 19 } return ans; 20 } 21 signed main(){ 22 cin>>n,prep(); 23 while(n) d[++len]=n&1,n>>=1;//轉化二進制 24 for(ll i=len,j;i;--i) if(d[i]){ 25 for(j=1;j<i;++j) //組合數就是隨便亂艸的算法 26 num[cnt+j]+=C[i-1][j]; 27 ++num[++cnt]; 28 } 29 for(ll i=1;i<=len;++i) //直接累乘就好 30 ans=ans*quick_pow(i,num[i])%mod; 31 cout<<ans<<endl; return 0; 32 }

?

?

?

?

2.數位dp

1 //by Judge 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #define ll long long 6 using namespace std; 7 const int M=55; 8 const int mod=1e7+7; 9 int cnt,x[M]; 10 ll n,f[M][2][M][M],num[M]; 11 inline ll quick_pow(ll x,ll p,ll ans=1){ 12 while(p) (p&1) && (ans=ans*x%mod),x=x*x%mod, p>>=1; 13 return ans; 14 } 15 ll dp(int cur,int up,int tmp,int d){ //記憶化深搜，log^2 n 無壓力 16 if(!cur) return tmp==d; //特判直接返回 17 if(~f[cur][up][tmp][d]) return f[cur][up][tmp][d]; // 已記憶，直接返回 18 int lim=up?x[cur]:1; 19 ll res=0; 20 for(int i=0;i<=lim;++i) //繼續深搜 21 res+=dp(cur-1,up&&i==lim,tmp+(i==1),d); 22 return f[cur][up][tmp][d]=res; //記憶化 23 } 24 ll solv(){ 25 while(n) x[++cnt]=n&1,n>>=1; //同上轉化 26 for(int i=1;i<=50;++i) //枚舉要放入的 1 的位數 27 memset(f,-1,sizeof(f)), 28 num[i]=dp(cnt,1,0,i); 29 ll res=1; 30 for(int i=1;i<=50;++i) //累乘進答案 31 res=res*quick_pow(i,num[i])%mod; 32 return res; 33 } 34 signed main(){ cin>>n,cout<<solv()<<endl; return 0; }

?

轉載于:https://www.cnblogs.com/Judge/p/9540939.html

總結

以上是生活随笔為你收集整理的花神的数论题（这题...哎。数位dp咋就这么 not naive 呢）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。