首页 > 代码库 > HDU 4507 (鬼畜级别的数位DP）
HDU 4507 (鬼畜级别的数位DP）
题目链接：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 longstruct status{ LL cnt,sum,sqsum; status() {cnt=-1;sum=sqsum=0;} status(LL cnt,LL sum,LL sqsum):cnt(cnt),sum(sum),sqsum(sqsum) {}}dp[20][10][10];LL digit[20],p[25];status dfs(int len,int re1,int re2,bool fp){ if(!len) return re1!=0&&re2!=0?status(1,0,0):status(0,0,0); if(!fp&&dp[len][re1][re2].cnt!=-1) return dp[len][re1][re2]; int fpmax=fp?digit[len]:9; status ans;ans.cnt=0; for(int i=0;i<=fpmax;i++) { if(i==7) continue; status next=dfs(len-1,(re1+i)%7,(re2*10+i)%7,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+((2*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=0; while(x) { digit[++len]=x%10; x/=10; } status tt=dfs(len,0,0,true); return tt.sqsum;}int main(){ int T; LL l,r; scanf("%d",&T); p[1]=1; for(int i=2;i<=20;i++) p[i]=(p[i-1]*10)%mod; while(T--) { scanf("%I64d%I64d",&l,&r); LL ans=f(r); ans-=f(l-1); 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）