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...
** **
/* ***********************************************
Author :111qqz
Created Time :2016年03月16日 星期三 10时44分58秒
File Name :code/hdu/4507.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const LL MOD = 1E9+7;
7LL l,r;
8int digit[30];
9LL power[40];
10struct node
11{
12 LL cnt,sum,sq;
13 node(){}
14 node (LL _cnt,LL _sum,LL _sq):
15 cnt(_cnt),sum(_sum),sq(_sq){};
16}dp[25][20][20];
17LL Add(LL a,LL b)
18{
19 LL res = (a+b) %MOD;
20 return res;
21}
22LL Mul(LL a,LL b)
23{
24 LL res = ((a%MOD)*(b%MOD))%MOD;
25 return res;
26}
27node dfs (int pos,int mod7,int sum7,bool limit)
28{
29 if (pos==0)
30 {
31 if (mod7!=0&&sum7!=0) return node(1,0,0);
32 else return node (0,0,0);
33 }
34 if (!limit&&dp[pos][mod7][sum7].cnt!=-1) return dp[pos][mod7][sum7];
1 int mx = limit?digit[pos]:9;
2 node res ;
3 res.cnt=res.sum=res.sq=0;
4 for ( int i = 0 ; i <= mx; i++)
5 {
6 if (i==7) continue;
7 node tmp = dfs(pos-1,(mod7+i)%7,(sum7*10+i)%7,limit&&i==mx);
8 res.cnt = Add(res.cnt,tmp.cnt);
9 res.sum = Add(res.sum,Add(tmp.sum,Mul(i,Mul(power[pos],tmp.cnt))));
10 res.sq = Add(res.sq,Add(tmp.sq,Mul(2*tmp.sum,i*power[pos])));
11 res.sq = Add(res.sq,Mul(i*power[pos],Mul(i*power[pos],tmp.cnt)));
12 }
13 if (!limit) dp[pos][mod7][sum7] = res;
14 return res;
15}
16LL solve ( LL n)
17{
18 int len = 0 ;
19 ms (digit,0);
20 while (n)
21 {
22 digit[++len] = n % 10;
23 n/=10;
24 }
25 return dfs(len,0,0,true).sq;
26}
1void pre()
2{
3 power[1] = 1;
4 for ( int i = 2 ;i <= 30 ; i++)
5 power[i] = (power[i-1]*10LL)%MOD;
6}
7int main()
8{
9#ifndef ONLINE_JUDGE
10 freopen("code/in.txt","r",stdin);
11#endif
12 pre();
13 int T;
14 cin>>T;
15 ms(dp,-1);
16 while (T--)
17 {
18 scanf("%lld %lld",&l,&r);
19 LL ans = solve (r) - solve (l-1);
20 while (ans<0) ans +=MOD;
21 // ans = ans % MOD;
22 printf("%lld\n",ans);
23 }
24#ifndef ONLINE_JUDGE
25 fclose(stdin);
26#endif
27 return 0;
28}