HDU 4507

数位DP。

一般是利用DFS来求数位DP了，结合了记忆化搜索。设dp[i][j][k]为前i位，并且前i位的数位和mod7为j,前i位的数字的表示数字值mod7。为什么可以这样呢？因为继续DFS下去，必定是得到一个不是7倍数的数的，因而，k这个位只是在确定叶子结点时有用的。

然后，可以这样选，求一个一些数的平方和（A+B）^2=A^2+2AB+B^2,由于B是可以是多个，因为会乘上一个cnt个数。

至于dp，记录的是当前状态下，其后续（因为是DFS）能得到的符合要求的个数，它们的和，以及它们的平方和。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL __int64
using namespace std;
const LL MOD=1000000007;
struct Node{
	LL cnt,msum,sqsum;
	void init(){
		cnt=-1,msum=0,sqsum=0;
	};
}dp[35][7][7];
LL l,r;
int num[35],len;
LL mod[35];


Node dfs(int len,int prem,int presqm,bool flag){
	if(len==0){
		Node st;
		st.init();
		if(prem&&presqm){
			st.cnt=1;
		} 
		else st.cnt=0;
		return st;
	}
	if(!flag&&dp[len][prem][presqm].cnt!=-1) return dp[len][prem][presqm];
	int up=flag?num[len]:9;
	Node ans;
	ans.init(); ans.cnt=0;
	for(int i=0;i<=up;i++){
		if(i==7) continue;
		Node st=dfs(len-1,(prem+i)%7,(presqm*10+i)%7,(flag&&i==up)?true:false);
		ans.cnt+=st.cnt;
		ans.cnt%=MOD;
		ans.msum=(ans.msum+st.msum+(st.cnt%MOD*(mod[len]*i)%MOD)%MOD)%MOD;
		ans.sqsum=(ans.sqsum+st.sqsum+((2*mod[len])%MOD*(i*st.msum)%MOD)%MOD)%MOD;
		ans.sqsum=(ans.sqsum+((mod[len]*i)%MOD*(i*mod[len])%MOD)%MOD*st.cnt)%MOD;
	}
	if(!flag) dp[len][prem][presqm]=ans;
	return ans;
}

LL slove(LL n){
	len=0;
	while(n){
		num[++len]=(int)(n%10);
		n/=10;
	}
	Node tmp=dfs(len,0,0,true);
	return tmp.sqsum;
}

int main(){
	int T;
	mod[1]=1;
	for(int i=2;i<35;i++){
		mod[i]=(mod[i-1]*10)%MOD;
	}
	scanf("%d",&T);
	while(T--){
		for(int i=0;i<35;i++){
				for(int k=0;k<7;k++){
					for(int l=0;l<7;l++)
					dp[i][k][l].init();
				}
		}
		scanf("%I64d%I64d",&l,&r);
		printf("%I64d
",((slove(r)-slove(l-1))%MOD+MOD)%MOD);
	}
	return 0;
}