[数位dp] bzoj 3209 花神的数论题

[数位dp] bzoj 3209 花神的数论题

题意：中文题。

思路：和普通数位dp一样，这里转换成二进制，然后记录有几个一。

统计的时候乘起来就好了。

代码：

#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"stack" #include"algorithm" #include"iostream" using namespace std; long long dp[66][66]; int m=10000007; int num[66]; long long dfs(int site,int n,int f) {if(site==0) return n?n:1; //注意是乘积。所以0个1的时候返回1if(!f&&dp[site][n]!=-1) return dp[site][n];int len=f?num[site]:1;long long ans=1; //ans 的初值是1for(int i=0;i<=len;i++){if(i==0) ans*=dfs(site-1,n,f&&i==len);else ans*=dfs(site-1,n+1,f&&i==len);if(ans>=m) ans%=m;}if(!f) dp[site][n]=ans%m;return ans%m; } long long solve(long long x) {int cnt=0;while(x){num[++cnt]=x%2;x/=2;}return dfs(cnt,0,1)%m; } int main() {long long n;memset(dp,-1,sizeof(dp));while(scanf("%lld",&n)!=-1){printf("%lld\n",solve(n));}return 0; }

posted on 2017-06-10 10:17 mthoutai 阅读(...) 评论(...) 编辑 收藏

转载于:https://www.cnblogs.com/mthoutai/p/6977992.html

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的[数位dp] bzoj 3209 花神的数论题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。