hdu 4507 吉哥系列故事——恨7不成妻 (返回平方和的数位dp)
题目链接 题意：如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍；
现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。
思路;如果是求count的话毫无难度。。。和之前的题目没什么区别。。不多说了。
但是是求平方数。。。一开始我的做法是在dfs中加一个LL 的参数表示当前的和，然后每次到dfs的出口，之前统计count的时候返回的是1，表示找到了满足条件的一个数，那这回就返回平方和。。但是这样做是错的。。。具体为什么错没有想得很明白。。。大概会少算？
然后参考了如下博客： hdu4507解题报告1 hdu4507解题报告2
正解是，之前的dp只统计了一个cnt,这回要同时统计cnt,sum,sqsum(平方和)..
我们先讨论如何求得满足条件的数的和。
我们设某次进入dfs的数是x,当前长度为pos（长度是越来越短的，因为是从高位到低位，对于没有处理到的低位，是按0算的，比如一个五位数xxxxx，第一次dfs以后也许得到4xxxx,x表示没有填的数的位置，实际上这个数就是40000），当前位置要防止的数字是i,考虑其位置，i对这个数的大小（不是和，就是最后要得到的一个数）的贡献是i*10^(pos-1),设为f. 那么当前的数就是f+x. 我们要求的就是所有f+x的和。现在我们考虑当新添加pos位的数字i对于和的贡献。
当新添加i时，相当与把之前的数整体左移了一位，相当于×10（因为之前[1,x]中的每个满足条件的数都乘了10，所以和也乘了10），然后对于新添加的i，它的贡献是i*cnt[x]，含义是对于之前[1,x]所有满足条件的每个数，都进行了pos位置填i的操作，所有对于所有满足条件的和一共添加了cnt[x]个i.
**如果写成用递推的式子就是 **
*sum[10*x+i] = 10 * sum[x] + cnt[x]i;//感谢@clq学长
如果用dfs的话式子就是
sum[new_state] = Σ{ sum[old_state] + (number to add at the postion) * (its base) * count[old_state] }。
接下来我们考虑维护平方和，方法类似。
(f**+x)^2=ff+xx+2fx.**
ff直接可以算，xx..其实就是上一层dfs得到的(f’+x’)^2嘛…也就是sum2[x] (sum2表示平方和)
2fx也可以算,x就是上一个状态的和。
同样，我们考虑现在已经有了x,处理到pos位置，填到该位置的数字是i的时候对平方和的影响。
xx部分在上一个状态处理过了，即为sum2[x], 2f*x 也可以通过sum[x]得到…
**注意ff,同样，对于之前的[1,x]中每个满足的数，都相当于第pos位添加了i,每个数对平方和的贡献都是ii,所以要*cnt[x]… **
以及要不断取模，为了方便写了两个函数来搞，代码看起来清楚一些。。。
哦，还有一个小坑。。取模相减以后可能为负数。。。。记得加MOD…
** **
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月16日 星期三 10时44分58秒
4File Name :code/hdu/4507.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const LL MOD = 1E9+7;
34LL l,r;
35int digit[30];
36LL power[40];
37struct node
38{
39 LL cnt,sum,sq;
40 node(){}
41 node (LL _cnt,LL _sum,LL _sq):
42 cnt(_cnt),sum(_sum),sq(_sq){};
43}dp[25][20][20];
44LL Add(LL a,LL b)
45{
46 LL res = (a+b) %MOD;
47 return res;
48}
49LL Mul(LL a,LL b)
50{
51 LL res = ((a%MOD)*(b%MOD))%MOD;
52 return res;
53}
54node dfs (int pos,int mod7,int sum7,bool limit)
55{
56 if (pos==0)
57 {
58 if (mod7!=0&&sum7!=0) return node(1,0,0);
59 else return node (0,0,0);
60 }
61 if (!limit&&dp[pos][mod7][sum7].cnt!=-1) return dp[pos][mod7][sum7];
62
63 int mx = limit?digit[pos]:9;
64 node res ;
65 res.cnt=res.sum=res.sq=0;
66 for ( int i = 0 ; i <= mx; i++)
67 {
68 if (i==7) continue;
69 node tmp = dfs(pos-1,(mod7+i)%7,(sum7*10+i)%7,limit&&i==mx);
70 res.cnt = Add(res.cnt,tmp.cnt);
71 res.sum = Add(res.sum,Add(tmp.sum,Mul(i,Mul(power[pos],tmp.cnt))));
72 res.sq = Add(res.sq,Add(tmp.sq,Mul(2*tmp.sum,i*power[pos])));
73 res.sq = Add(res.sq,Mul(i*power[pos],Mul(i*power[pos],tmp.cnt)));
74 }
75 if (!limit) dp[pos][mod7][sum7] = res;
76 return res;
77}
78LL solve ( LL n)
79{
80 int len = 0 ;
81 ms (digit,0);
82 while (n)
83 {
84 digit[++len] = n % 10;
85 n/=10;
86 }
87 return dfs(len,0,0,true).sq;
88}
89
90void pre()
91{
92 power[1] = 1;
93 for ( int i = 2 ;i <= 30 ; i++)
94 power[i] = (power[i-1]*10LL)%MOD;
95}
96int main()
97{
98#ifndef ONLINE_JUDGE
99 freopen("code/in.txt","r",stdin);
100#endif
101 pre();
102 int T;
103 cin>>T;
104 ms(dp,-1);
105 while (T--)
106 {
107 scanf("%lld %lld",&l,&r);
108 LL ans = solve (r) - solve (l-1);
109 while (ans<0) ans +=MOD;
110 // ans = ans % MOD;
111 printf("%lld\n",ans);
112 }
113#ifndef ONLINE_JUDGE
114 fclose(stdin);
115#endif
116 return 0;
117}