题意：如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
1、整数中某一位是7；2、整数的每一位加起来的和是7的整数倍；3、这个整数是7的整数倍；现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。分析：数位DP，关键内容如下。
(pre0+i)%7用于处理各个位数之和时候为7的倍数，(pre1*10+i)%7用于处理这个数是否为7的倍数。
#include<iostream>using namespace std;const __int64 mod=1000000007;struct Node{__int64 c; //和7无关的数的个数__int64 sum; //和7无关的数的和__int64 sqsum; //和7无关的数的平方和};Node dp[20][10][10]; //分别表示待处理数的位数，各位数字和是7的倍数，数本身是7的倍数int bit[20];//存储待处理数的每位__int64 p[20];//p[i]=10^i,p[0]=1void init(){int i,j,k;p[0]=1;for(i=1;i<20;i++)p[i]=(p[i-1]*10)%mod;for(i=0;i<20;i++)for(j=0;j<10;j++)for(k=0;k<10;k++)dp[i][j][k].c=-1;}Node DFS(int pos,int pre0,int pre1,bool fg){Node ans,tmp;int end,i;if(pos==-1)//数位已处理完，并判断pre0及pre1{tmp.c=pre0 && pre1;tmp.sum=tmp.sqsum=0;return tmp;}if(!fg && dp[pos][pre0][pre1].c!=-1) //注意边界return dp[pos][pre0][pre1];end=fg?bit[pos]:9;ans.c=ans.sum=ans.sqsum=0;for(i=0;i<=end;i++){if(i==7) continue; //跳过7，，有7即不合法tmp=DFS(pos-1,(pre0+i)%7,(pre1*10+i)%7,fg&&i==end);ans.c+=tmp.c;ans.c%=mod;ans.sum+=(tmp.sum+((p[pos]*i)%mod)*tmp.c%mod)%mod;ans.sum%=mod;ans.sqsum+=(tmp.sqsum+((2*p[pos]*i)%mod)*tmp.sum)%mod;ans.sqsum%=mod;ans.sqsum+=((tmp.c*p[pos])%mod*p[pos]%mod*i*i%mod);ans.sqsum%=mod;}if(!fg) dp[pos][pre0][pre1]=ans; //要判断边界return ans;}__int64 cal(__int64 n){int pos=0;while(n){bit[pos++]=n%10;n/=10;}return DFS(pos-1,0,0,true).sqsum;}int main(){int T;__int64 l,r,ans;scanf("%d",&T);init();while(T–){scanf("%I64d%I64d",&l,&r);ans=cal(r);ans-=cal(l-1);ans=(ans%mod+mod)%mod;//注意这里的写法，否则会出错，因为减法可能会出现负数printf("%I64d\n",ans);}return 0;}
但我想说，我做了一个善良的平凡女子，并且一直在爱，
