题目链接：HDOJ4507

这个题，跟标准模板就有很多的不一样了，主要体现在数学的计算上面


题意：区间【L，R】内，与7数字无关的数的平方和

无关的定义是：该数不含7，不能被7整除，各个数位之和不是7的倍数


分析：

如果是统计符合某种性质的数的个数，那么很简单

不含7，在数位枚举的时候遇到7跳过就好

被7整除和数位之和是7的倍数，都是在数位枚举完了之后，记忆化的时候一个IF判断就好

就是模板


统计数的和的题都没有做过，直接上平方和，怎么做呢？

很简单：先从和来想

之前有多少个数符合了要求，每个数位上的值是多少，先加起来


平方和呢：（a+b）^2=a^2+b^2+2*a*b

（a + b）^2 = a^2 + 2*a*b + b^2可以得出(数位上的对应值 * (能满足的条件的数的数量) + 2 * sigma(（每个分支下面满足条件的数量）*(分支和)) + sigma(分支平方和）。

所以，要求平方和，各个数的和也得先求出来


按照这个思路，dp【pos】【sum】【num】就需要做改动，变成一个结构体

需要保存三个数：当前满足条件的数的个数，数的和，数的平方和

所以，需要预处理每一个数位上的值，每个数位在表示数的时候是有权值的，十位数上的数权重为10，以此类推

预处理权重数组




#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

const long long MOD=1000000007LL;

struct Node{
	long long cnt;
	long long sum;
	long long sqsum;
}dp[20][10][10];
int digit[20];
long long p[20];

Node dfs(int pos,int sum,int num,bool flag){
	Node ans,tmp;
	if (pos==0){
		tmp.cnt=(sum!=0&&num!=0);
		tmp.sum=tmp.sqsum=0;
		return tmp;
	}
	if (flag&&dp[pos][sum][num].cnt!=-1) return dp[pos][sum][num];
	int maxnumber=flag?9:digit[pos];
	ans.cnt=ans.sum=ans.sqsum=0;
	for(int i=0;i<=maxnumber;i++){
		if (i==7) continue;
		tmp=dfs(pos-1,(sum+i)%7,(num*10+i)%7,flag||i<maxnumber);
		
		ans.cnt+=tmp.cnt;
		ans.cnt%=MOD;
		
		ans.sum+=(tmp.sum+((p[pos]*i)%MOD)*tmp.cnt%MOD)%MOD;
		ans.sum%=MOD;
		
		ans.sqsum+=(tmp.sqsum+((2*p[pos]*i)%MOD)*tmp.sum)%MOD;
		ans.sqsum%=MOD;
		ans.sqsum+=(tmp.cnt*p[pos])%MOD*p[pos]%MOD*i*i%MOD;
		ans.sqsum%=MOD;

	}
	if (flag) dp[pos][sum][num]=ans;
	return ans;
}

long long calc(long long n){
	int len=0;
	while(n){
		digit[++len]=n%10;
		n/=10;
	}
	return dfs(len,0,0,0).sqsum;
}

int main(){
	//input;
	int T;
	long long l,r,ans;
	p[1]=1;
	for(int i=2;i<20;i++)
		p[i]=(p[i-1]*10)%MOD;
	memset(dp,0,sizeof(dp));
	for(int i=0;i<20;i++)
		for(int j=0;j<10;j++)
			for(int k=0;k<10;k++)
				dp[i][j][k].cnt=-1;
	scanf("%d",&T);
	while(T--){
		scanf("%I64d%I64d",&l,&r);
		ans=calc(r);
		ans-=calc(l-1);
		ans=(ans%MOD+MOD)%MOD;
		printf("%I64d\n",ans);
	}
	return 0;
}