题目意思： 给定一个区间，求这段区间中，不含7，对7取余为0，各个位数相加之和对7取余为0的数的平方和。
设d[i][j][k][m]代表长度为i的，对7取余为j的，各个位数相加之和对7取余为k的数的平方和，
但是算平方和需要用到这些数的和，这些数的个数。所以用了一个结构体数组保存每种状态的Count，sum1,.sum2;
(ago+k1)^2+(ago+k2)^2+(ago+k3)^2=3*ago^2+2*ago*(k1+k2+k3)+k2^2+k2^2+k3^2;
=Count1*ago^2+2*ago*sum1+sum2;
需要注意取模运算和long long
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define MOD 1000000007
#define maxn 20
using namespace std;
const int N=;
LL md[N];
LL digit[maxn];
LL ans=;
struct node
{
LL Count=,sum1=,sum2=;
};
node dp[maxn][][][];
int visit[maxn][][][];
node dfs(int len,int pre,int before, int state,bool fp) //dfs版本的纯属暴力枚举每一个数字,而递推版本的是考虑了前缀的影响
{
if(state)
{
node temp;
temp.Count=;
temp.sum1=;
temp.sum2=;
return temp;
}
if(len== && (pre== || before==))
{
node temp;
temp.Count=;
temp.sum1=;
temp.sum2=;
return temp;
}
else if(len==)
{
node temp;
temp.Count=;
temp.sum1=;
temp.sum2=;
return temp;
}
if(!fp && visit[len][pre][before][state]== ) //
{
return dp[len][pre][before][state];
}
node ret ;
int fpmax = fp ? digit[len] : ;
for(int i=;i<=fpmax;i++) //分别算出以i开头的数的方案数，
{
node next=dfs(len-,(((pre*+i))%) ,(before+i)%,i== | state,fp && i == fpmax);
//temp=temp%MOD;
//ret+=(temp*temp)%MOD;
LL ago = ( i*md[len-] )%MOD;
ret.Count = (ret.Count + next.Count) %MOD;
ret.sum1 = (ret.sum1 + ( ago*next.Count ) %MOD + next.sum1) %MOD;
ret.sum2 = ( ret.sum2 + (next.Count* ( (ago*ago )%MOD ) ) %MOD +(*ago*next.sum1)%MOD + next.sum2 ) %MOD;
}
if(!fp)
{
dp[len][pre][before][state]= ret;
visit[len][pre][before][state]=;
}
return ret;
} LL f(LL n)
{
int len=;
while(n)
{
digit[++len] = n % ;
n /= ;
}
LL ans=;
ans+=dfs(len,,,,true).sum2;
return ans;
}
void init()
{
memset(visit,,sizeof(visit));
}
int main()
{
// freopen("test.txt","r",stdin);
int t;
scanf("%d",&t);
md[]=;
for(int i=;i<=N;i++)
md[i]=(md[i-]*)%MOD;
while(t--)
{
init();
LL n,m;
scanf("%I64d%I64d",&n,&m);
LL ans1=f(m);
LL ans2=f(n-);
printf("%I64d\n", (ans1-ans2 + MOD)%MOD );
}
return ;
}