首页 > 代码库 > HDU 4507 吉哥系列故事――恨7不成妻(数位DP+结构体)
HDU 4507 吉哥系列故事――恨7不成妻(数位DP+结构体)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4507
题目大意:如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关
1、整数中某一位是7;
2、整数的每一位加起来的和是7的整数倍;
3、这个整数是7的整数倍;
求一定区间内和7无关的数字的平方和。
解题思路:这里我们用一个结构体分别存储符合条件的数的个数n,从当前位开始至末尾的数值s(比如一个数当前为1234***,*表示还不知道的位值,代表的就是***),从当前位开始至末尾的数的平方和sq(比如一个数当前为1234***,代表的就是(***)x(***))。我们用结构体dp[pos][mod1][mod2]来记录状态。因为可以保证如果当前位置!满足limit并且mod1和mod2都相等,那么最后的得到的sq都是相同的。
我们可以利用下一位的n,s,sq,退出上一位n,s,sq,其间存在递推关系。比如234(n=1,s,sq)怎么推到6234?那就是s2=s+6*10^3,sq=2*(6*10^3)*234+(6*10^3)*(6*10^3);
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 typedef unsigned long long ll; 6 const ll MOD=1e9+7; 7 int a[25]; 8 ll power[25]; 9 struct node{ 10 ll n,s,sq;//符合条件的数的个数,各位值之和,平方和 11 }dp[25][10][10]; 12 13 node dfs(ll pos,ll mod1,ll mod2,bool limit){//每次的value不一样,不能直接存平方和的值之和 14 if(pos==0){ 15 node t; 16 t.n=(mod1&&mod2); 17 t.s=t.sq=0; 18 return t; 19 } 20 if(!limit&&dp[pos][mod1][mod2].n!=-1) return dp[pos][mod1][mod2]; 21 node ans,temp; 22 ans.n=ans.s=ans.sq=0; 23 int up=limit?a[pos]:9; 24 for(int i=0;i<=up;i++){ 25 if(i==7) continue; 26 temp = dfs(pos-1,(mod1*10+i)%7,(mod2+i)%7,limit && (i == up)); 27 ans.n=(ans.n + temp.n)%MOD; 28 ans.s=(ans.s+temp.s+((i*power[pos])%MOD *temp.n) % MOD) % MOD; 29 ans.sq=(ans.sq+temp.sq+((2*i*power[pos])%MOD*temp.s)%MOD)%MOD; 30 ans.sq=(ans.sq+(((i*i*power[pos])%MOD*power[pos])%MOD*temp.n)%MOD)%MOD; 31 } 32 if(!limit) dp[pos][mod1][mod2]=ans; 33 return ans; 34 } 35 36 ll solve(ll n){ 37 ll top=0; 38 while(n){ 39 a[++top]=n%10; 40 n/=10; 41 } 42 node ans=dfs(top,0,0,true); 43 return ans.sq; 44 } 45 46 int main(){ 47 memset(dp,-1,sizeof(dp)); 48 power[1]=1; 49 for(int i=2;i<=19;i++){ 50 power[i]=(power[i-1]*10)%MOD; 51 } 52 int t; 53 scanf("%d",&t); 54 while(t--){ 55 ll l,r,ans; 56 scanf("%lld %lld",&l,&r); 57 ans=(solve(r)-solve(l-1)+MOD)%MOD;//可能出现负数,所以要补回来 58 printf("%lld\n",ans); 59 } 60 return 0; 61 }
HDU 4507 吉哥系列故事――恨7不成妻(数位DP+结构体)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。