(题目链接)
题意
求区间${[a,b]}$中的某些数的平方和，这些数要满足1.不是7的倍数，2.不含有7这个数字，3.所有数位上的数加起来不是7的倍数
Solution
貌似记忆化搜索会好写的多→_→
虽然是求平方和，但是要求满足的性质都很符合数位dp的尿性，所以我们记3个东西：平方和，和，个数。然后直接做就可以了。
细节
LL
代码
// hdu4507#include#include #include #include #include #include #include #define LL long long#define inf (1ll<<30)#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL bin[30],l,r;int vis[20][7][7][2],t[20],n;struct data {LL x,y,z;}f[20][7][7][2];data dfs(int pos,int s,int r,int c,int lim) { if (!pos) { if (!c && s && r) return (data){1,0,0}; else return (data){0,0,0}; } if (!lim && vis[pos][s][r][c]) return f[pos][s][r][c]; int end=lim ? t[pos] : 9; data ans=(data){0,0,0}; for (int i=0;i<=end;i++) { data tmp=dfs(pos-1,(s+i)%7,(r*10+i)%7,c|(i==7),lim && i==end); LL add=i*bin[pos-1]; (ans.x+=tmp.x)%=MOD; //个数 (ans.y+=tmp.y+add*tmp.x)%=MOD; //和 (ans.z+=tmp.z+add*tmp.x%MOD*add%MOD+2*tmp.y%MOD*add%MOD)%=MOD; //平方和 } if (!lim) vis[pos][s][r][c]=1,f[pos][s][r][c]=ans; return ans;}LL solve(LL x) { for (n=0;x;x/=10) t[++n]=x%10; return dfs(n,0,0,0,1).z;}int main() { bin[0]=1;for (int i=1;i<=20;i++) bin[i]=bin[i-1]*10%MOD; int T;scanf("%d",&T); while (T--) { scanf("%lld%lld",&l,&r); LL ans=solve(r)-solve(l-1); printf("%lld\n",(ans+MOD)%MOD); } return 0;}