题目链接：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 |