hdu 4507 数位dp(求和,求平方和)[通俗易懂]

hdu 4507 数位dp(求和,求平方和)

大家好,又见面了,我是全栈君。

http://acm.hdu.edu.cn/showproblem.php?pid=4507

Problem Description
  单身!

  依旧单身!

  吉哥依旧单身!

  DS级码农吉哥依旧单身!
  所以。他生平最恨情人节,无论是214还是77。他都讨厌!
  
  吉哥观察了214和77这两个数,发现:
  2+1+4=7
  7+7=7*2
  77=7*11
  终于,他发现原来这一切归根究竟都是由于和7有关!所以,他如今甚至讨厌一切和7有关的数。

  什么样的数和7有关呢?

  假设一个整数符合以下3个条件之中的一个。那么我们就说这个整数和7有关——
  1、整数中某一位是7。
  2、整数的每一位加起来的和是7的整数倍。
  3、这个整数是7的整数倍;

  如今问题来了:吉哥想知道在一定区间内和7无关的数字的平方和。

 


Input
输入数据的第一行是case数T(1 <= T <= 50),然后接下来的T行表示T个case;每一个case在一行内包括两个正整数L, R(1 <= L <= R <= 10^18)。

 


Output
请计算[L,R]中和7无关的数字的平方和。并将结果对10^9 + 7 求模后输出。
 


Sample Input
   
   
3 1 9 10 11 17 17

 


Sample Output
   
   
236 221 0

 

/***
hdu 4507  数位dp(求和,求平方和)
解题思路:dp[len][sum1][sum2] 表示长度为len对7取模为sum1。各位上的数字和为sum2有多少个满足的数
          一个是与7无关的数的个数。就是简单的数位DP了,非经常规。

第二个与7无关的数的和的维护须要用到第一个个数。 处理到第pos个数位时,加上i*10^pos * 后面的个数 第三个的维护须要用到前面两个 (pre*10^pos + next)^2= (pre*10^pos)^2+2*pre*10^pos*next +next^2*/#include <stdio.h>#include <algorithm>#include <string.h>#include <iostream>using namespace std;typedef long long LL;const LL mod=1e9+7;LL l,r,p[25];int bit[25];struct node{ LL cnt,sum,sqsum;} dp[25][10][10];node dfs(int len,int sum1,int sum2,int flag){ if(len<0) { node tmp; tmp.cnt=(sum1!=0&&sum2!=0); tmp.sum=tmp.sqsum=0; return tmp; } if(flag==0&&dp[len][sum1][sum2].cnt!=-1)return dp[len][sum1][sum2]; node ans,tmp; int end=flag?bit[len]:9; ans.cnt=ans.sqsum=ans.sum=0; for(int i=0; i<=end; i++) { if(i==7)continue; tmp=dfs(len-1,(sum1+i)%7,(sum2*10+i)%7,flag&&i==end); ans.cnt+=tmp.cnt; ans.cnt%=mod; ans.sum+=(tmp.sum+i*p[len]%mod*tmp.cnt%mod)%mod; ans.sum%=mod; ans.sqsum+=(tmp.sqsum+2*p[len]*i%mod*tmp.sum%mod)%mod; ans.sqsum%=mod; ans.sqsum+=(tmp.cnt*p[len]%mod*p[len]%mod*i*i%mod); ans.sqsum%=mod; } if(flag==0)dp[len][sum1][sum2]=ans; return ans;}LL solve(LL n){ int len=0; while(n) { bit[len++]=n%10; n/=10; } return dfs(len-1,0,0,1).sqsum;}int main(){ p[0]=1; for(int i=1; i<20; i++) p[i]=(p[i-1]*10)%mod; for(int i=0; i<25; i++) { for(int j=0; j<10; j++) { for(int k=0; k<10; k++) { dp[i][j][k].cnt=-1; } } } int T; scanf("%d",&T); while(T--) { scanf("%I64d%I64d",&l,&r); printf("%I64d\n",((solve(r)-solve(l-1))%mod+mod)%mod); } return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116251.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • gcc命令和make命令[通俗易懂]

    gcc命令和make命令[通俗易懂]针对gcc,新建一个c语言文件:3.常用的有两个命令:-o将main.c预处理、编译、汇编并链接形成可执行文件main。-o选项用来指定输出文件的文件名。-S把.c文件编译成汇编文件.s查看汇编文件:其他还有把.s文件输出为.o文件的命令-c把.o文件链接为可执行文件的命令也是-o…

    2022年10月11日
  • 绝对成交课程培训_成交的5大关键

    绝对成交课程培训_成交的5大关键影响力集团培训讲师孟昭春http://blog.sina.com.cn/mengzhaochun第一天下午一个思想:把自己能把握的事情把握就能实现把握不了的目标。1.孟老师从自身做法出发讲出:他下面的销售人员问他问题他从来不给答案,只是指墙(墙上有5问5答)。2.大客户特点:金额大、周期比较长、内部决策者多。3.用户的四个拒绝:我不需要、我不着急、我不相信、我没钱。(70%顾客…

    2022年10月24日
  • 解决ajax跨域问题【5种解决方案】「建议收藏」

    解决ajax跨域问题【5种解决方案】「建议收藏」什么是跨域问题?跨域问题来源于JavaScript的”同源策略”,即只有协议+主机名+端口号(如存在)相同,则允许相互访问。也就是说JavaScript只能访问和操作自己域下的资源,不能访问和操作其他域下的资源。跨域问题是针对JS和ajax的,html本身没有跨域问题。查看浏览器开发者工具Console报错:Failedtoloadhttp://a.a.com:8080/A/…

  • html静态页面代码_静态网页设计代码

    html静态页面代码_静态网页设计代码这个例子我们做一个游戏静态页面,自动跳转到我们想要玩的游戏或者视频等网站大家也可以根绝我的代码,适当修改一些信息,但是套用我的这个模板请注释下来自我这,我也是初学者,辛辛苦苦写了几个小时,尊重下劳动成果先看效果图:我以张杰为背景图,里面是各种网站跳转,比如我点击:冰火人,他就会跳转到4399的冰火人游戏界面。ok,上代码,我觉得比较简单,就没注释,希望能看懂:<!DOCTYPEhtml><html><headlang=”en”><metacha

  • 怎么用ps提取图片颜色分析色彩搭配

    怎么用ps提取图片颜色分析色彩搭配这个小工具(PS插件)还是挺好用的,无需网络,直接在PS软件上面即可使用,支持Win与MAC版PSCS6以上版本,再也不用为分析图片配色发愁了,这个PS脚本插件可以搜一下“图片颜色分析识别PS插件Win/Mac版”即可找到。1、安装PS脚本(插件),选中PS软件图标右键“属性”-“打开文件位置”-“Presets”-“Scripts”复制脚本(.jsx)到以上目录粘贴。2、打开PS软件,打开我们…

  • hdoj 2602 Bone Collector 【01背包】

    hdoj 2602 Bone Collector 【01背包】

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号