首页 > 代码库 > hdu 4507 吉哥系列故事——恨7不成妻

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

http://acm.hdu.edu.cn/showproblem.php?pid=4507

用dp结构体里面存有符合要求的个数cnt,各位数和的sum1,符合要求的数的平方和sum2三个值。在维护sum2时需要用到sum1和cnt两个值。

数位dp

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define LL __int64 5 using namespace std; 6 const LL mod=1000000007; 7  8 struct node 9 {10     LL cnt;11     LL sum1;12     LL sum2;13 } dp[30][30][30];14 int num[30];15 LL c[30];16 17 node dfs(int pos,int sum1,int sum2,bool flag)18 {19     if(pos==-1)20     {21         node st;22         st.cnt=(sum1!=0&&sum2!=0);23         st.sum1=0;24         st.sum2=0;25         return st;26     }27     if(!flag&&dp[pos][sum1][sum2].cnt!=-1) return dp[pos][sum1][sum2];28     node ans;29     ans.cnt=0;30     ans.sum1=0;31     ans.sum2=0;32     node st1;33     int xx=flag?num[pos]:9;34     for(int i=0; i<=xx; i++)35     {36         if(i==7) continue;37         st1=dfs(pos-1,(sum1+i)%7,(sum2*10+i)%7,flag&&(i==xx));38         ans.cnt+=st1.cnt;39         ans.cnt%=mod;40         ans.sum1+=(st1.sum1+((c[pos]*i%mod)*st1.cnt)%mod)%mod;41         ans.sum1%=mod;42         ans.sum2+=(((st1.cnt*c[pos])%mod*c[pos]%mod*i*i)%mod);43         ans.sum2%=mod;44         ans.sum2+=(st1.sum2+((2*c[pos]*i)%mod)*st1.sum1)%mod;45         ans.sum2%=mod;46     }47     if(!flag) dp[pos][sum1][sum2]=ans;48     return ans;49 }50 51 LL get(LL n)52 {53     int cnt=0;54     while(n)55     {56         num[cnt++]=n%10;57         n=n/10;58     }59     node a=dfs(cnt-1,0,0,true);60     return a.sum2;61 }62 63 void inti()64 {65     c[0]=1;66     for(int i=1; i<20; i++)67     {68         c[i]=(c[i-1]*10)%mod;69     }70     for(int i=0; i<20; i++)71     {72         for(int j=0; j<20; j++)73         {74             for(int k=0; k<20; k++)75             {76               dp[i][j][k].cnt=-1;77             }78         }79     }80 }81 int main()82 {83     int t;84     scanf("%d",&t);85     inti();86     while(t--)87     {88         LL n,m;89         scanf("%I64d%I64d",&n,&m);90         printf("%I64d\n",((get(m)-get(n-1))%mod+mod)%mod);91     }92     return 0;93 }
View Code

 

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