hdu4507 数位dp+推公式

推公式的能力需要锻炼。。

/*

dp的时候要存结构体

里面三个元素：

cnt，就是满足条件的个数

sum1，就是满足条件的数字和

sum2，满足条件的数字平方和

推导过程：还是用记忆化搜索模板

    dp[pos][mod1][mod2]:后pos位模7=mod1，数位和模7=mod2的状态

    设当前状态cur

    枚举当前位i，碰到7跳过

        求出后pos-1位的状态nxt

        这里需要建立当前数的模型：

            设x是后pos-1位的数：i*10^len+x;

        cur.cnt+=nxt.cnt;

        cur.sum1+=nxt.sum1+nxt.cnt*(i*10^(pos-1))

        cur.sum2+=sum{ (i*10^len+x)^2 }= sum{ (i*10^len)^2 }+sum{ x^2 }+sum{ 2*x*i*10^len }

        化简上式：sum{ x^2 }=nxt.sum2,

                  sum{ 2*x*i*10^len }=nxt.sum1*2*i*10^len

                  sum{ (i*10^len)^2 }=nxt.cnt*(i*10^len)

*/

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 1000000007

struct Node{

    ll cnt,sum1,sum2;

    Node(){cnt=-;sum1=sum2=;}

    Node(ll cnt,ll sum1,ll sum2):cnt(cnt),sum1(sum1),sum2(sum2){}

}dp[][][];

ll a[],f[];

Node dfs(ll pos,ll mod1,ll mod2,ll lim){

    if(pos<=) return mod1&&mod2?Node(,,):Node(,,);//% 7 ≠0 即可

    if(!lim && dp[pos][mod1][mod2].cnt!=-)return dp[pos][mod1][mod2];

    int num=lim?a[pos]:;

    Node cur;cur.cnt=;

    for(int i=;i<=num;i++){

        if(i==)continue;

        Node nxt=dfs(pos-,(mod1*+i)%,(mod2+i)%,lim&&i==num);

        cur.cnt=(cur.cnt+nxt.cnt)%mod;

        cur.sum1=((cur.sum1+nxt.sum1)%mod+nxt.cnt*(i*f[pos]%mod)%mod)%mod;

        ll tmp1=nxt.sum1*%mod*i%mod*f[pos]%mod;

        ll tmp2=nxt.cnt*(i*f[pos]%mod)%mod*(i*f[pos]%mod)%mod;

        cur.sum2=((cur.sum2+nxt.sum2)%mod+(tmp1+tmp2%mod)%mod)%mod;

    }

    if(!lim)dp[pos][mod1][mod2]=cur;

    return cur;

}

ll query(ll x){

    int len=;

    while(x){a[++len]=x%;x/=;}

    return dfs(len,,,).sum2;

}

int main(){

    f[]=;for(int i=;i<=;i++)f[i]=f[i-]*%mod;

    ll A,B,t;cin>>t;

    while(t--){

        cin>>A>>B;

        cout<<(query(B)-query(A-)+mod)%mod<<endl;

    }

}