B - 吉哥系列故事——恨7不成妻

单身!

　　依然单身！

　　吉哥依然单身！

　　DS级码农吉哥依然单身！

　　所以，他生平最恨情人节，不管是214还是77，他都讨厌！

　　

　　吉哥观察了214和77这两个数，发现：

　　2+1+4=7

　　7+7=72

　　77=711

　　最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！

　　什么样的数和7有关呢？

　　如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——

　　1、整数中某一位是7；

　　2、整数的每一位加起来的和是7的整数倍；

　　3、这个整数是7的整数倍；

　　现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。

Input

输入数据的第一行是case数T(1 <= T <= 50)，然后接下来的T行表示T个case;每个case在一行内包含两个正整数L, R(1 <= L <= R <= 10^18)。

Output

请计算[L,R]中和7无关的数字的平方和，并将结果对10^9 + 7 求模后输出。

Sample Input

3

1 9

10 11

17 17

Sample Output

236

221

0

不能出现7的,平方和比较麻烦，要把他按平方公式拆开计算

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include <iomanip>

#include<cmath>

#include<float.h>

#include<string.h>

#include<algorithm>

#define sf scanf

#define pf printf

#define sca(x) scanf("%d",&x)

#define mm(x,b) memset((x),(b),sizeof(x))

#include<vector>

#include<queue>

#include<map>

#define rep(i,a,n) for (int i=a;i<n;i++)

#define per(i,a,n) for (int i=a;i>=n;i--)

typedef long long ll;

const ll mod=1e9+7;

const double eps=1e-8;

using namespace std;

const double pi=acos(-1.0);

const int inf=0xfffffff;

const int N=1000005;

struct node

{

	ll cnt;//ÊýµÄ¸öÊý

	ll sum;//¸÷ÊýÖ®ºÍ

	ll ssum;//Âú×ãÌõ¼þµÄÊýƽ·½Ö®ºÍ

	node(int a=-1,int b=0,int c=0) { cnt=a;sum=b;ssum=b; }//³õʼ»¯

}dp[25][12][12];

ll p[25];

int num[25];

void first()

{

	p[0]=1;

	rep(i,1,21)

		p[i]=(p[i-1]*10)%mod;

}

node dfs(ll pos,ll sum,ll ssum,ll limit)//λÊý£¬Î»ÊýºÍ%7£¬ÊýÖµ%7£¬ÊÇ·ñÊÇÉÏÏÞ

{

	node ans;

	ans.cnt=0;

	if(pos==0)

	{

		if(limit=1&&sum!=0&&ssum!=0)

		ans.cnt=1;

		return ans;

	}

	if(!limit&&dp[pos][sum][ssum].cnt!=-1) return dp[pos][sum][ssum];

	int up=limit?num[pos]:9;

	for(int i=0;i<=up;i++){

        if(i==7)continue;

        node next=dfs(pos-1,(i+sum)%7,(ssum*10+i)%7,limit&&(i==up) );

        ans.cnt+=next.cnt;

        ans.cnt%=mod;

        ans.sum+=(next.cnt*i%mod*p[pos-1 ]%mod+next.sum )%mod;

        ans.sum%=mod;

        ans.ssum+=(next.ssum+2*(p[pos-1]*next.sum%mod*i)%mod  )%mod;

        ans.ssum%=mod;

        ans.ssum+=(p[pos-1]*p[pos-1]%mod*next.cnt%mod*i*i)%mod;

        ans.ssum%=mod;

    }

	if(!limit)

	dp[pos][sum][ssum]=ans;

	return ans;

}

ll solve(ll n)

{

	int pos=0;

	ll x=n;

	while(x)

	{

		num[++pos]=x%10;

		x/=10;

	}

	//mm(dp,-1);

	node ans=dfs(pos,0,0,1);

	return ans.ssum;

}

int main()

{

	first();ll l,r;

	int re;

	sf("%d",&re);

	while(re--)

	{

		sf("%lld%lld",&l,&r);

		pf("%lld\n",((solve(r)-solve(l-1))%mod+mod)%mod);

	}

	return 0;

}