首页 > 代码库 > 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+结构体)