注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4507 吉哥系列故事——恨7不成妻  

2014-07-21 15:04:09|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4507
题意:
找区间内和7无关数的平方和。
满足以下条件之一就认为和7有关:
数字中含有7;
各位数字和能被7整除;
该数能被7整除。
题解:
数位dp。看cxlove的推导才知道怎么算平方和部分。
当前位置数为i,数字有pos位,后面的数为x,则数为x+i*10^(pos-1),记f=i*10^(pos-1),求各数的平方和展开变为:
f^2+2*f*x+x^2,其中sigma(x^2)是题目要维护的部分,sigma(2*f*x)相当于2*f*sigma(x),sigm(f^2)相当于f^2*总个数,这样我们需要维护三个东西:sigma(x^2), sigma(x), 与7无关的个数。

struct Node{
LL cnt; //与7无关数的个数
LL ss; //与7无关数的和
LL sqss; //与7无关数的平方和
}f[20][8][8]; //处理的数位,每位数之和余7,数余7
int num[20];
LL P[20];

void init()
{
P[0]=1;
for(int i=1;i<20;i++)
P[i]=(P[i-1]*10)%MOD;
for(int i=0;i<20;i++)
for(int j=0;j<8;j++)
for(int k=0;k<8;k++)
f[i][j][k].cnt=-1;
}

Node dfs(int pos,int r1,int r2,int e) //r1记录每位数之和余7,r2记录整个数余7
{
if(pos == -1)
{
Node tmp;
tmp.cnt=tmp.ss=tmp.sqss=0;
if(r1!=0 && r2!=0)
tmp.cnt=1;
return tmp;
}
if(!e && f[pos][r1][r2].cnt!=-1)
return f[pos][r1][r2];
Node tmp,res;
res.cnt=res.ss=res.sqss=0;
int u=e?num[pos]:9;
for(int d=0;d<=u;d++)
{
if(d == 7) continue;
tmp=dfs(pos-1,(r1+d)%7,(r2*10+d)%7,e && d==u);
res.cnt=(res.cnt+tmp.cnt)%MOD;
res.ss=((res.ss+tmp.ss)%MOD+((tmp.cnt*d)%MOD*P[pos])%MOD)%MOD;
res.sqss=((res.sqss+tmp.sqss)%MOD+((2*d*P[pos])%MOD*tmp.ss)%MOD+(((d*d*P[pos])%MOD*P[pos])%MOD*tmp.cnt)%MOD)%MOD;
}
if(!e)
f[pos][r1][r2]=res;
return res;
}

LL solve(LL a)
{
int len=0;
while(a)
{
num[len++]=a%10;
a/=10;
}
return dfs(len-1,0,0,1).sqss;
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
int T;
LL L,R;
init();
sf(T);
while(T--)
{
sf264(L,R);
pf64((solve(R)-solve(L-1)+MOD)%MOD);
}
return 0;
}

  评论这张
 
阅读(1009)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017