这道题吧，在数位DP中还是有一些难度的。正因如此，我从这道题开始就放弃了递推式的打法（dfs大法好！）
学习dfs的打法是看的这篇博客
然后来看一下这道题，与其他简单的题不同的是，这道题最后要求的是平方和而不是数字个数了。对此，我们可以存三个变量
1.与7无关的数的数量cnt
2.与7无关的数之和sum1
3.与7无关的数的的平方和sum2重要的是公式的推导：从上一位（x）推导到这一位（y）
（10*x+y）^2=100x^2+y^2+20*x*y
若设这一位（pos）为ans（数字为i），更低的一位为tmp
就有这样的转移：
ans.cnt+=tmp.cnt
ans.sum1+=tmp.cnt*i*power[pos]+tmp.sum1
ans.sum2+=i*power[pos]*i*power[pos]*tmp.cnt+tmp.sum2+2*i*power[pos]*tmp.sum1
cnt其实就是原来求个数的思想，累加就好，sum1和sum2注意每次还要乘上tmp的个数再加上后面那一串东西，因为满足pos这一位是i的有tmp.cnt那么多个，既然是求所有与7无关的数的和，当然所有的都要算上
注意！
每一步都要取模，不然极可能爆LL
#include<bits/stdc++.h> #define INF 2100000000 #define mod 1000000007 #define LL long long using namespace std; int len=0; LL read()//LL!!! { LL x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } struct wei{ LL cnt,sum1,sum2;//个数，和，平方和 }dp[20][10][10]; LL num[20],power[23]; wei dfs(int pos,int mod1,int mod2,int lim) { if(pos==0) { wei tmp={0,0,0}; if(mod1&&mod2)tmp.cnt=1;//满足每位相加的和不是7的倍数，同时这个数不是7的倍数才可产生贡献 return tmp; } if(!lim&&dp[pos][mod1][mod2].cnt!=-1) return dp[pos][mod1][mod2]; LL maxx=lim?num[pos]:9; wei ans;ans.cnt=0,ans.sum1=0,ans.sum2=0; for(int i=0;i<=maxx;++i)//枚举当前位（pos）的数 { if(i==7) continue; wei tmp=dfs(pos-1,(mod1+i)%7,(mod2*10+i)%7,(lim&&i==maxx));//用更低位来更新 ans.cnt=(ans.cnt+tmp.cnt)%mod; ans.sum1=(ans.sum1+(i*power[pos]%mod*tmp.cnt%mod+tmp.sum1)%mod)%mod; // ans.sum2+=(tmp.cnt*i*power[pos]*i*power[pos])+tmp.sum2+2*i*power[pos]*tmp.sum1; ans.sum2=(ans.sum2+(i*power[pos]%mod*i%mod*power[pos]%mod*tmp.cnt%mod+tmp.sum2)%mod+2*i%mod*power[pos]%mod*tmp.sum1%mod)%mod; } if(!lim) dp[pos][mod1][mod2]=ans;//没有顶上界，说明0~9都取了才能更新答案 return ans; } LL solve(LL x) { if(!x)return 0; memset(dp,-1,sizeof(dp)); len=0; while(x) num[++len]=x%10,x/=10; return dfs(len,0,0,1).sum2%mod; } int main() { // freopen("seven.in","r",stdin); // freopen("seven.out","w",stdout); int T=read(); power[1]=1; for(int i=2;i<=20;++i) power[i]=power[i-1]*10%mod; while(T--) { LL m=read(),n=read(); //printf("%lld %lld ",m,n); printf("%lld ",((solve(n)-solve(m-1))%mod+mod)%mod); } } /* 3 1 9 10 11 17 17 */
纪念一下开启数位DP的dfs打法~