题解 恨7不成妻

前言

好题，真是好题，真是奋斗了摸了两天才勉强做出来的好题。

感谢fr大佬的讲解，对数位dp加深了不少理解。深刻发现：菜鸡打了300+行代码，大佬100行就解决了，效率还更高。太菜了(* ￣︿￣)！

题解

这么明显的提示，很容易就能发现是数位dp吧

这道题第一次我做的时候有困难，我就去请教了fr大佬。经大佬指教之后，感觉新的解法和旧的解法有比较大的区别。这里就不提原本的解法，直接讲优化后的解法

(dp)式子

观察题面，我们不难发现：这道题居然求的不是个数，不是和，而是平方和，一时间感觉很难递推。

由于是递归，我们在求解(k)位的时候，(k-1)的情况已经推完了

我们设第(k)位为(A)，设(k-1位)为(B)，利用完全平方公式

由于事实上一个状态由多个状态递推过来，所以实际上

(sum a^2)需要利用到前一个状态的个数；

(sum 2times a times b)中可以提取(sum 2times a)作为公因数，剩下的(sum b)需要利用到前一个状态的和

(sum b^2)需要利用到前一个状态的平方和

因此我们需要同时维护三个(dp)

(f[i][j][k])记录的是数字的各个数位上的数字之和(mod 7 = i)，数字(mod 7 = j)，的(k)位数的个数

(g[i][j][k])记录的是数字的各个数位上的数字之和(mod 7 = i)，数字(mod 7 = j)，的(k)位数的和

(h[i][j][k])记录的是数字的各个数位上的数字之和(mod 7 = i)，数字(mod 7 = j)，的(k)位数的平方和

且(ti+pmod 7 =i),(tj+ptimes 10^{k-1}mod 7 =j)

进一步推出(Rightarrow)

emm，dp推完了！ˋ( ° ▽、° )

tips:dp过程中，无需考虑零的位置。也就是说，由前置零的情况也被计算进去了

数位dp求解

经过fr大佬指点，认识到了数位dp更优秀的求解方法

从高位向低位直接枚举，然后通过限制"前缀"的方法，时候后面的数字可以自由组合，充分利用上了dp

举例说明，以3245为例：

1. 从最高为——千位开始，由于千位上是3，因此分别尝试0,1,2,后面的3位数可以自由组合
2. 第二高位是百位，数字是2，那么就尝试30,31,后面2位数字自由组合
3. 之后是十位，数字是4，尝试320,321,322,323，后面一位数自由组合。
4. 只剩最后一位了，暴力枚举即可

我之前做的时候，特意在dp中避免了前缀零的情况，导致了dp推导麻烦，数位求解也麻烦。欸，是我太菜了{{{(>_<)}}}

完整代码

code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const ll MOD=1e9+7;
ll f[7][7][25],g[7][7][25],h[7][7][25],tim[45],tims[45];
int T;

void init();
inline void inc(ll&,ll);
ll calc(ll);

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    #endif

    init();

    scanf("%d",&T);
    while(T--){
        ll l,r; cin>>l>>r;
        ll ansl=calc(l-1ll),ansr=calc(r);
        cout<<(((ansr-ansl)%MOD+MOD)%MOD)<<endl;
    }

    return 0;
}

void init(){
    ll tmp=1;
    for(int i=0;i<=40;++i) {tim[i]=tmp; tmp*=10ll; tmp%=MOD;}
    tmp=1;
    for(int i=0;i<=40;++i) {tims[i]=tmp; tmp*=10ll; tmp%=7ll;}

    for(int i=0;i<=9;++i) if(i!=7){
        f[i%7][i%7][1]++;
        g[i%7][i%7][1]+=i;
        h[i%7][i%7][1]+=i*i;
    }
    for(int k=2;k<=20;++k){
        for(int i=0;i<=6;++i){
            for(int j=0;j<=6;++j){
                for(int p=0;p<=9;++p){
                    if(p==7) continue;
                    ll tmp;
                    inc(f[i][j][k],f[((i-p%7)%7+7)%7][((j+7-p*tims[k-1])%7+7)%7][k-1]);
                    tmp=p*tim[k-1]; tmp=tmp%MOD;
                    tmp=(tmp % MOD)*(f[((i-p%7)%7+7)%7][((j+7-p*tims[k-1])%7+7)%7][k-1] % MOD); tmp%=MOD;
                    inc(g[i][j][k],tmp);
                    inc(g[i][j][k],g[((i-p%7)%7+7)%7][((j+7-p*tims[k-1])%7+7)%7][k-1]);
                    tmp=p; tmp%=MOD; tmp*=tmp; tmp%=MOD;
                    tmp*=f[((i-p%7)%7+7)%7][((j+7-p*tims[k-1])%7+7)%7][k-1]; tmp%=MOD;
                    tmp*=tim[2*k-2]; tmp%=MOD;
                    inc(h[i][j][k],tmp);
                    tmp=2ll*p*tim[k-1]; tmp%=MOD;
                    tmp*=g[((i-p%7)%7+7)%7][((j+7-p*tims[k-1])%7+7)%7][k-1]; tmp%=MOD;
                    inc(h[i][j][k],tmp);
                    inc(h[i][j][k],h[((i-p%7)%7+7)%7][((j+7-p*tims[k-1])%7+7)%7][k-1]);
                }
            }
        }
    }
}

inline void inc(ll& a,ll b){
    (a+=b)>=MOD?a-=MOD:a;
}

ll calc(ll num){
    ll ans=0;
    if(num<10){
        for(int i=1;i<=num;++i){
            if(i==7) continue;
            ans+=i*i;
        }
        return ans;
    }

    int line[20]; line[0]=0;
    while(num) {line[++line[0]]=num%10; num/=10;}
    ll add=0,sum=0;
    for(int k=line[0];k>=2;--k){
        for(int p=0;p<=line[k]-1;++p){
            if(p==7) continue;
            add+=p; sum=sum*10ll+p;
            for(int i=0;i<=6;++i){
                if((add+i)%7==0) continue;
                for(int j=0;j<=6;++j){
                    if((sum%7ll*tims[k-1]+j)%7==0) continue;
                    // h[i][j][k]+=f[((i-p%7)%7+7)%7][((j+7-p*tims[k-1])%7+7)%7][k-1]*p*p*tim[2*k-2];
                    // h[i][j][k]+=2*p*tim[k-1]*g[((i-p%7)%7+7)%7][((j+7-p*tims[k-1])%7+7)%7][k-1];
                    // h[i][j][k]+=h[((i-p%7)%7+7)%7][((j+7-p*tims[k-1])%7+7)%7][k-1];
                    ll tmp=sum; tmp%=MOD; tmp*=tmp; tmp%=MOD;
                    tmp*=f[i][j][k-1]; tmp%=MOD;
                    tmp*=tim[2*k-2]; tmp%=MOD;
                    inc(ans,tmp);
                    tmp=2ll*sum; tmp%=MOD;
                    tmp*=tim[k-1]; tmp%=MOD;
                    tmp*=g[i][j][k-1]; tmp%=MOD;
                    inc(ans,tmp);
                    inc(ans,h[i][j][k-1]);
                }
            }
            add-=p; sum-=p; sum/=10ll;
        }
        if(line[k]==7) return ans;
        add+=line[k]; sum=sum*10ll+line[k];
    }

    for(int p=0;p<=line[1];++p){
        if(p==7) continue;
        if((add+p)%7==0) continue;
        if((sum*tims[1]+p)%7==0) continue;
        ll tmp=sum*tim[1]+p; tmp%=MOD; tmp*=tmp; tmp%=MOD;
        inc(ans,tmp);
    }
    return ans;
}