数位DP HDU 4507 求满足条件的平方和

这跟我的上一篇数位DP博客，有点相似，仔细想一下就能明白：

博客：https://blog.csdn.net/qq_42211531/article/details/86307936

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>
#define MT(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const double E=2.718281828459;
const ll MOD=1e9+7;
const int INF=0x3f3f3f3f;

struct node
{
    ll cnt;
    ll sum;
    ll qsum;
} ans_sum,dp[20][10][10];

ll pre[25],num[25];

node dfs(ll pos,ll mod,ll sum,bool lead,bool limit)
{
    if(pos==0)
        return node{mod&&sum,0,0};
    if(!lead&&!limit&&dp[pos][mod][sum].cnt!=-1)
        return dp[pos][mod][sum];
    ll up=limit?num[pos]:9;
    node ans= {0,0,0};
    for(ll i=0; i<=up; i++)
    {
        if(i==7)
            continue;
        node next=dfs(pos-1,(mod*10+i)%7,(sum+i)%7,lead&&i==0,limit&&i==num[pos]);
        ans.cnt+=next.cnt;
        ans.cnt%=MOD;
        ans.sum+=(next.sum+next.cnt*i%MOD*pre[pos]%MOD)%MOD;
        ans.sum%=MOD;
        ans.qsum+=(next.qsum+2*pre[pos]%MOD*i%MOD*next.sum%MOD)%MOD;
        ans.qsum%=MOD;
        ans.qsum+=(next.cnt*i%MOD*i%MOD*pre[pos]%MOD*pre[pos]%MOD)%MOD;
        ans.qsum%=MOD;
    }
    if(!lead&&!limit)
        dp[pos][mod][sum]=ans;
    return ans;
}

ll solve(ll x)
{
    ll sign=0;
    while(x)
    {
        num[++sign]=x%10;
        x=x/10;
    }
    memset(dp,-1,sizeof(dp));
    ans_sum=dfs(sign,0,0,1,1);
    return ans_sum.qsum;
}

void init()
{
    pre[1]=1;
    for(int i=2; i<=20; i++)
        pre[i]=(pre[i-1]*10ll)%MOD;
    return ;
}

int main()
{
    init();
    ll l,r,t;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld %lld",&l,&r);
        printf("%lld\n",((solve(r)-solve(l-1))%MOD+MOD)%MOD);
    }
    return 0;
}