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
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const LL MOD = 1E9+7;
LL l,r;
int digit[30];
LL power[40];
struct node
{
LL cnt,sum,sq;
node(){}
node (LL _cnt,LL _sum,LL _sq):
cnt(_cnt),sum(_sum),sq(_sq){};
}dp[25][20][20];
LL Add(LL a,LL b)
{
LL res = (a+b) %MOD;
return res;
}
LL Mul(LL a,LL b)
{
LL res = ((a%MOD)*(b%MOD))%MOD;
return res;
}
node dfs (int pos,int mod7,int sum7,bool limit)
{
if (pos==0)
{
if (mod7!=0&&sum7!=0) return node(1,0,0);
else return node (0,0,0);
}
if (!limit&&dp[pos][mod7][sum7].cnt!=-1) return dp[pos][mod7][sum7];
int mx = limit?digit[pos]:9;
node res ;
res.cnt=res.sum=res.sq=0;
for ( int i = 0 ; i <= mx; i++)
{
if (i==7) continue;
node tmp = dfs(pos-1,(mod7+i)%7,(sum7*10+i)%7,limit&&i==mx);
res.cnt = Add(res.cnt,tmp.cnt);
res.sum = Add(res.sum,Add(tmp.sum,Mul(i,Mul(power[pos],tmp.cnt))));
res.sq = Add(res.sq,Add(tmp.sq,Mul(2*tmp.sum,i*power[pos])));
res.sq = Add(res.sq,Mul(i*power[pos],Mul(i*power[pos],tmp.cnt)));
}
if (!limit) dp[pos][mod7][sum7] = res;
return res;
}
LL solve ( LL n)
{
int len = 0 ;
ms (digit,0);
while (n)
{
digit[++len] = n % 10;
n/=10;
}
return dfs(len,0,0,true).sq;
}
void pre()
{
power[1] = 1;
for ( int i = 2 ;i <= 30 ; i++)
power[i] = (power[i-1]*10LL)%MOD;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
pre();
int T;
cin>>T;
ms(dp,-1);
while (T--)
{
scanf("%lld %lld",&l,&r);
LL ans = solve (r) - solve (l-1);
while (ans<0) ans +=MOD;
// ans = ans % MOD;
printf("%lld\n",ans);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}