题解|恨7不成妻

这题要求的是符合一些条件的数，明显是数位dp的套路，所以我们就向数位dp方面想。

先来看条件：

1.整数中不能有7。处理方式非常简单，就是当枚举到7时直接continue掉就行了

2.整数的每一位加起来的和不是7的整数。这个也很简单，在dp数组和dfs中加入一个记录当前每一位的和的维度就行了。

3.这个整数不是7的整数倍。在转移过程中，假设我们的原数是a，要新增的数字是b，那么我们的新数就是a*10+b，继续增加一个维度来记录。

对于这一题来说，处理条件并不大难，有难度的地方在数字的平方和的维护。维护平方和需要我们在转移的过程中记录三个值：

1.与7无关的数字个数。这一个值的记录只要简单地进行数位dp就行。

2.与7无关的数字的和。这一个值的记录需要用到第一个值，具体转移的方程是：

    sum(现在的值)=pre_sum(dfs回溯的值)+p_pos(上限第pos位的数字)*i(当前选择的数字)*pre_cnt(后面的数字个数)

3.与7无关的数字的平方和。这一个值的记录需要用到前两个值，方程如下（经过完全平方公式分解后的）：

    sqsum(现在的平方和)=pre_sqsum(回溯的平方和)+(pre_cnt*p_pos*p_pos*i*i+2*p_pos*i*pre_sum)

接下来就是代码实践了。注意多组数据和取模。

#include<cstdio>
#include<cstring>
const long long MOD=1e9+7;
struct num{
    long long cnt,sum,sqsum;
}dp[20][10][10];
long long t,p[20],bit[20],l,r;
num dfs(int pos,int pre1,int pre2,bool flag)
{
    if(pos==-1)
    {
        num ff;
        ff.cnt=(pre1!=0 && pre2!=0);
        ff.sum=ff.sqsum=0;
        return ff;
    }
    if(!flag&&dp[pos][pre1][pre2].cnt!=-1)return dp[pos][pre1][pre2];
    int end=flag?bit[pos]:9;
    num ans,ff;
    ans.cnt=ans.sqsum=ans.sum=0;
    for(int i=0;i<=end;i++)
    {
        if(i==7)continue;
        ff=dfs(pos-1,(pre1+i)%7,(pre2*10+i)%7,flag&&i==end);
        ans.cnt+=ff.cnt;
        ans.cnt%=MOD;
        ans.sum+=(ff.sum+((p[pos]*i)%MOD)*ff.cnt%MOD)%MOD;
        ans.sum%=MOD;
        ans.sqsum+=(ff.sqsum+((2*p[pos]*i)%MOD)*ff.sum)%MOD;
        ans.sqsum%=MOD;
        ans.sqsum+=((ff.cnt*p[pos])%MOD*p[pos]%MOD*i*i%MOD);
        ans.sqsum%=MOD;
    }
    return !flag?dp[pos][pre1][pre2]=ans:ans;
}
long long part(long long n)
{
    int pos=0;
    while(n)bit[pos++]=n%10,n/=10;
    return dfs(pos-1,0,0,1).sqsum;
}
int main()
{
    p[0]=1;
    for(int i=1;i<20;i++)p[i]=(p[i-1]*10)%MOD;
    memset(dp,-1,sizeof(dp));
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&l,&r);
        long long ans=part(r);
        ans-=part(l-1);
        ans=(ans%MOD+MOD)%MOD;
        printf("%lld\n",ans);
    }
}