HDU 4507 (鬼畜级别的数位DP)

时间:2022-09-01 13:23:09

题目链接: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)的更多相关文章

  1. HDU 5787 K-wolf Number (数位DP)

    K-wolf Number 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5787 Description Alice thinks an integ ...

  2. 【HDU 3652】 B-number (数位DP)

    B-number Problem Description A wqb-number, or B-number for short, is a non-negative integer whose de ...

  3. HDU 5787 K-wolf Number(数位DP)

    [题目链接] http://acm.hdu.edu.cn/showproblem.php?pid=5787 [题目大意] 求区间[L,R]内十进制数相邻k位之间不相同的数字的个数. [题解] 很显然的 ...

  4. 2017&quot&semi;百度之星&quot&semi;程序设计大赛 - 复赛1005&amp&semi;&amp&semi;HDU 6148 Valley Numer【数位dp】

    Valley Numer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  5. HDU 4352 XHXJ&&num;39&semi;s LIS 数位dp lis

    目录 题目链接 题解 代码 题目链接 HDU 4352 XHXJ's LIS 题解 对于lis求的过程 对一个数列,都可以用nlogn的方法来的到它的一个可行lis 对这个logn的方法求解lis时用 ...

  6. HDU 2089 不要62(数位dp模板题)

    http://acm.hdu.edu.cn/showproblem.php?pid=2089 题意:求区间内不包含4和连续62的数的个数. 思路: 简单的数位dp模板题.给大家推荐一个好的讲解博客.h ...

  7. hdu 4352 XHXJ&&num;39&semi;s LIS 数位dp&plus;状态压缩

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4352 XHXJ's LIS Time Limit: 2000/1000 MS (Java/Others ...

  8. HDU 2089(暴力和数位dp)

    传送门: http://acm.hdu.edu.cn/showproblem.php?pid=2089 不要62 Time Limit: 1000/1000 MS (Java/Others)    M ...

  9. Hdu 3652 B-number &lpar;同余数位DP&rpar;

    题目链接: Hdu 3652 B-number 题目描述: 给出一个数n,问 [1, n]区间内有几个数能被13整除并且还有13这个子串? 解题思路: 能整除的数位DP,确定好状态随便搞搞就能过了.d ...

随机推荐

  1. UITabBarController的创建与自定义TarBar---学习笔记三

    代码如下: #import <UIKit/UIKit.h> @interface BSJTabBarViewController : UITabBarController @end #im ...

  2. js MATH

    MATH Math 对象用于执行数学任务. 无需创建它,通过把 Math 作为对象使用就可以调用其所有属性和方法. Math 对象属性 var a=Math.E; //输出2.718281828459 ...

  3. 哈希 poj 1480

    计算可能的数目 a3*x3^3+a4*x4^3+a5*x5^5=-(a1*x1^3+a2*x2^3); 列举右边的  结果存到数组  z[i] 和为i的右边等式的数目 如果和小于0  +2500000 ...

  4. matlab 调用VLfeat库开篇问题

    准备工作见此网站 :http://cnyubin.com/?p=85 保存关闭startup.m文件后 重新打开matlab后 在命令行输入path或者vl_version无法检测到库已安装到matl ...

  5. Java沙箱技术

    自从Java技术出现以来,有关Java平台的安全性及由Java技术发展所引发的新的安全性问题,引起了越来越多的关注.目前,Java已经大量应用在各个领域,研究Java的安全 性对于更好地使用Java具 ...

  6. 当年的笔记&lowbar;apache配置虚拟主机

    下午需要,在网上找了一堆,没找到合适的,翻出来自己当年的笔记,还是自己记的容易理解. 解决方案1:通过端口来区分 1>添加一个虚拟主机1.在d盘下新建www目录,如:d:/www. 2.修改ht ...

  7. Ellipse常用快捷键

    Ctrl+m:视窗大小变化 Ctrl+F6:在打开的文件件进行切换 Ctrl+F7:在资源窗口间切换Ctrl+F8:在各种模式下进行切换 Ctrl+e:选择某个打开的文件Shift+home:整行选取 ...

  8. Oracle 客户端 NLS&lowbar;LANG 的设置&lpar;转&rpar;

    1. NLS_LANG 参数组成NLS_LANG参数由以下部分组成:NLS_LANG=<Language>_<Territory>.<Clients Characters ...

  9. java 采用MD5加密解密

    MD5加密解密 package endecrypt; import java.io.UnsupportedEncodingException; import java.security.Message ...

  10. TextView &plus; Spanned实现图文混排以及图片点击交互

    最近要实现图文混排的需求,webview过大,所以想到了用SpannableStringBuilder来实现. 不过参考了大量国内文章,大多数是教你如何实现图文混排,并没有提及图片点击交互的.有翻阅了 ...