http://acm.hdu.edu.cn/showproblem.php?pid=4507
用dp结构体里面存有符合要求的个数cnt，各位数和的sum1，符合要求的数的平方和sum2三个值。在维护sum2时需要用到sum1和cnt两个值。
数位dp
1 #include2 #include 3 #include 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 }