题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4507
题目大意:求指定范围内与7不沾边的所有数的平方和。结果要mod 10^9+7(鬼畜の元凶)
解题思路:
与7不沾边的数需要满足三个条件。
①不出现7
②各位数和不是7的倍数
③这个数不是7的倍数
这三个条件都是基础的数位DP。
但是这题要统计的不是符合条件个数,而是平方和。
也就是说在DP时候,要重建每个数,算出平方,然后求和。
需要维护三个值(推荐使用结构体), 假定dfs推出返回的结构体是next,当前结果的结构体是ans
①符合条件数的个数 cnt
②符合条件数的和 sum
③符合添加数的平方和 sqsum
其中①是基础数位DP。②next.sum+(10^len*i)*ans.cnt,其中(10^len*i)*ans.cnt代表以len为首位的这部分数字和。
③首先重建一下这个数,(10^len*i+x),其中x是这个数的后面部分,则平方和就是(10^len*i)^2+x^2+2*10^len*i*x,其中x^2=next.sqsum
整体还要乘以next.cnt,毕竟不止一个。
这样sqsum+=next.sqsum
sqsum+=(2*10^len*i*x)*next.cnt=(2*10^len*i)*next.sum(神奇的化简)
sqsum+=(10^len*i)^2*next.cnt
然后就是本题鬼畜的地方了,cnt,sum,sqsum,三个都是达到了int64极限。
也即是说凡是这三个值参与运算的地方,都要狠狠打上mod,尤其是cnt!一坨坨mod出现了。
mod之后统计函数也有个小陷阱,那就是f(r)在mod之后有可能小于f(l-1)。也就是要对负数取正数模。
负数取模的方法(ans%mod+mod)%mod。
#include "cstdio"
#include "math.h"
#include "cstring"
#define mod 1000000007LL
#define LL long long
struct status
{
LL cnt,sum,sqsum;
status() {cnt=-;sum=sqsum=;}
status(LL cnt,LL sum,LL sqsum):cnt(cnt),sum(sum),sqsum(sqsum) {}
}dp[][][];
LL digit[],p[];
status dfs(int len,int re1,int re2,bool fp)
{
if(!len) return re1!=&&re2!=?status(,,):status(,,);
if(!fp&&dp[len][re1][re2].cnt!=-) return dp[len][re1][re2];
int fpmax=fp?digit[len]:;
status ans;ans.cnt=;
for(int i=;i<=fpmax;i++)
{
if(i==) continue;
status next=dfs(len-,(re1+i)%,(re2*+i)%,fp&&i==fpmax);
ans.cnt+=next.cnt;
ans.cnt%=mod;
ans.sum+=(next.sum+((p[len]*i)%mod)*next.cnt%mod)%mod;
ans.sum%=mod;
ans.sqsum+=(next.sqsum+((*p[len]*i)%mod)*next.sum)%mod;
ans.sqsum%=mod;
ans.sqsum+=((next.cnt*p[len])%mod*p[len]%mod*i*i%mod);
ans.sqsum%=mod;
}
if(!fp) dp[len][re1][re2]=ans;
return ans;
}
LL f(LL x)
{
int len=;
while(x)
{
digit[++len]=x%;
x/=;
}
status tt=dfs(len,,,true);
return tt.sqsum;
}
int main()
{
int T;
LL l,r;
scanf("%d",&T);
p[]=;
for(int i=;i<=;i++) p[i]=(p[i-]*)%mod;
while(T--)
{
scanf("%I64d%I64d",&l,&r);
LL ans=f(r);
ans-=f(l-);
printf("%I64d\n",(ans%mod+mod)%mod);
}
}
11814266 | 2014-10-07 00:19:33 | Accepted | 4507 | 15MS | 276K | 1527 B | C++ | Physcal |
HDU 4507 (鬼畜级别的数位DP)的更多相关文章
-
HDU 5787 K-wolf Number (数位DP)
K-wolf Number 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5787 Description Alice thinks an integ ...
-
【HDU 3652】 B-number (数位DP)
B-number Problem Description A wqb-number, or B-number for short, is a non-negative integer whose de ...
-
HDU 5787 K-wolf Number(数位DP)
[题目链接] http://acm.hdu.edu.cn/showproblem.php?pid=5787 [题目大意] 求区间[L,R]内十进制数相邻k位之间不相同的数字的个数. [题解] 很显然的 ...
-
2017";百度之星";程序设计大赛 - 复赛1005&;&;HDU 6148 Valley Numer【数位dp】
Valley Numer Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Tota ...
-
HDU 4352 XHXJ&#39;s LIS 数位dp lis
目录 题目链接 题解 代码 题目链接 HDU 4352 XHXJ's LIS 题解 对于lis求的过程 对一个数列,都可以用nlogn的方法来的到它的一个可行lis 对这个logn的方法求解lis时用 ...
-
HDU 2089 不要62(数位dp模板题)
http://acm.hdu.edu.cn/showproblem.php?pid=2089 题意:求区间内不包含4和连续62的数的个数. 思路: 简单的数位dp模板题.给大家推荐一个好的讲解博客.h ...
-
hdu 4352 XHXJ&#39;s LIS 数位dp+状态压缩
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4352 XHXJ's LIS Time Limit: 2000/1000 MS (Java/Others ...
-
HDU 2089(暴力和数位dp)
传送门: http://acm.hdu.edu.cn/showproblem.php?pid=2089 不要62 Time Limit: 1000/1000 MS (Java/Others) M ...
-
Hdu 3652 B-number (同余数位DP)
题目链接: Hdu 3652 B-number 题目描述: 给出一个数n,问 [1, n]区间内有几个数能被13整除并且还有13这个子串? 解题思路: 能整除的数位DP,确定好状态随便搞搞就能过了.d ...
随机推荐
-
UITabBarController的创建与自定义TarBar---学习笔记三
代码如下: #import <UIKit/UIKit.h> @interface BSJTabBarViewController : UITabBarController @end #im ...
-
js MATH
MATH Math 对象用于执行数学任务. 无需创建它,通过把 Math 作为对象使用就可以调用其所有属性和方法. Math 对象属性 var a=Math.E; //输出2.718281828459 ...
-
哈希 poj 1480
计算可能的数目 a3*x3^3+a4*x4^3+a5*x5^5=-(a1*x1^3+a2*x2^3); 列举右边的 结果存到数组 z[i] 和为i的右边等式的数目 如果和小于0 +2500000 ...
-
matlab 调用VLfeat库开篇问题
准备工作见此网站 :http://cnyubin.com/?p=85 保存关闭startup.m文件后 重新打开matlab后 在命令行输入path或者vl_version无法检测到库已安装到matl ...
-
Java沙箱技术
自从Java技术出现以来,有关Java平台的安全性及由Java技术发展所引发的新的安全性问题,引起了越来越多的关注.目前,Java已经大量应用在各个领域,研究Java的安全 性对于更好地使用Java具 ...
-
当年的笔记_apache配置虚拟主机
下午需要,在网上找了一堆,没找到合适的,翻出来自己当年的笔记,还是自己记的容易理解. 解决方案1:通过端口来区分 1>添加一个虚拟主机1.在d盘下新建www目录,如:d:/www. 2.修改ht ...
-
Ellipse常用快捷键
Ctrl+m:视窗大小变化 Ctrl+F6:在打开的文件件进行切换 Ctrl+F7:在资源窗口间切换Ctrl+F8:在各种模式下进行切换 Ctrl+e:选择某个打开的文件Shift+home:整行选取 ...
-
Oracle 客户端 NLS_LANG 的设置(转)
1. NLS_LANG 参数组成NLS_LANG参数由以下部分组成:NLS_LANG=<Language>_<Territory>.<Clients Characters ...
-
java 采用MD5加密解密
MD5加密解密 package endecrypt; import java.io.UnsupportedEncodingException; import java.security.Message ...
-
TextView + Spanned实现图文混排以及图片点击交互
最近要实现图文混排的需求,webview过大,所以想到了用SpannableStringBuilder来实现. 不过参考了大量国内文章,大多数是教你如何实现图文混排,并没有提及图片点击交互的.有翻阅了 ...