题目意思： 给定一个区间，求这段区间中，不含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=20; LL md[N]; LL digit[maxn]; LL ans=0; struct node { LL Count=0,sum1=0,sum2=0; }; node dp[maxn][7][7][2]; int visit[maxn][7][7][2]; node dfs(int len,int pre,int before, int state,bool fp) //dfs版本的纯属暴力枚举每一个数字,而递推版本的是考虑了前缀的影响 { if(state) { node temp; temp.Count=0; temp.sum1=0; temp.sum2=0; return temp; } if(len==0 && (pre==0 || before==0)) { node temp; temp.Count=0; temp.sum1=0; temp.sum2=0; return temp; } else if(len==0) { node temp; temp.Count=1; temp.sum1=0; temp.sum2=0; return temp; } if(!fp && visit[len][pre][before][state]== 1) // { return dp[len][pre][before][state]; } node ret ; int fpmax = fp ? digit[len] : 9 ; for(int i=0;i<=fpmax;i++) //分别算出以i开头的数的方案数， { node next=dfs(len-1,(((pre*10+i))%7) ,(before+i)%7,i==7 | state,fp && i == fpmax); //temp=temp%MOD; //ret+=(temp*temp)%MOD; LL ago = ( i*md[len-1] )%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 +(2*ago*next.sum1)%MOD + next.sum2 ) %MOD; } if(!fp) { dp[len][pre][before][state]= ret; visit[len][pre][before][state]=1; } return ret; } LL f(LL n) { int len=0; while(n) { digit[++len] = n % 10; n /= 10; } LL ans=0; ans+=dfs(len,0,0,0,true).sum2; return ans; } void init() { memset(visit,0,sizeof(visit)); } int main() { // freopen("test.txt","r",stdin); int t; scanf("%d",&t); md[0]=1; for(int i=1;i<=N;i++) md[i]=(md[i-1]*10)%MOD; while(t--) { init(); LL n,m; scanf("%I64d%I64d",&n,&m); LL ans1=f(m); LL ans2=f(n-1); printf("%I64d ", (ans1-ans2 + MOD)%MOD ); } return 0; }