【2018.06.26NOIP模拟】T2号码bachelor

题目描述

Mike 正在在忙碌地发着各种各样的的短信。旁边的同学 Tom 注意到，Mike 发出短信的接收方手机号码似乎都满足着特别的性质，难道Mike 的好朋友是满足正态分布的？Tom 很好奇。

由于 Mike 有着自己最喜欢的数字 a ，并且 a 的范围是：2≤a≤9 。Tom 从这里入手，发现了一些端倪，假设 Mike 发的电话号码是一个十进制数字 S ，Tom 发现 S 会满足以下三个性质中的一个：
1．S 是 a 的倍数。
2．S 在十进制表示下的各项数字加起来是 a 的倍数。
3．S 的某一位是 a 。
比如说当 a=7 时，21，16，17 这三个数字组成的电话号码都是会被Mike发短信的，他们分别满足 1，2，3 性质。

Tom 在想：如果给你两个自然数 L，R，以及 Mike 最喜欢的数字 a ，在 [L,R] 中有多少个号码是 Mike 要发短信的手机号码，只需要你告诉他这些数字的平方和。比如说 3，7 是合法的，那么你应该输出 32 + 72 = 58 这个数。

当然，由于答案可能很大，你只需要将答案对 109 + 7 取模即可。

输入格式

输入的第一行包括一个正整数 T ，表示总共有 T 组询问。
接下来有 T 行，每行三个整数 L，R，A 。

输出格式

输出包括 T 行，每行一个整数，表示对 10^9 + 7 取模的答案。

输入

3
2 20 6
3 203 7
11 771 2

输出

1884
1593269
32817226

备注

【数据范围】
对于 15% 的数据，0≤L≤R≤10^6，T=1
对于 35% 的数据，0≤L≤R≤10^7，T=1
另外有 25% 的数据，A=2；L=10^k；R=10^v；k和v都是自然数。
对于 100% 的数据，0≤L≤R≤10^18；2≤A≤9；T≤100

【2018.06.26NOIP模拟】T2号码bachelor 【数位DP】*-LMLPHP

#include<bits/stdc++.h>

using namespace std;

#define Mod 1000000007

#define LL long long

int f0[20][10][10][2][2];

int f1[20][10][10][2][2];

int f2[20][10][10][2][2];

//f0个数 f1和 f2平方和

//位数 数位的和 数的大小 是否出现过 是否满位

int a[20],n,m;

LL l,r;

void divide(LL x){

    n=0;

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

    for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);

}

int dp(LL x){

    if(x<=0)return 0;

    memset(f0,0,sizeof(f0));

    memset(f1,0,sizeof(f1));

    memset(f2,0,sizeof(f2));

    divide(x);

    for(int i=0;i<a[1];i++){

        f0[1][i%m][i%m][(i==m)][0]+=1;

        f1[1][i%m][i%m][(i==m)][0]+=i;

        f2[1][i%m][i%m][(i==m)][0]+=i*i;

    }

    f0[1][a[1]%m][a[1]%m][a[1]==m][1]+=1;

    f1[1][a[1]%m][a[1]%m][a[1]==m][1]+=a[1];

    f2[1][a[1]%m][a[1]%m][a[1]==m][1]+=a[1]*a[1];

    for(int i=1;i<n;i++)

    for(int j=0;j<m;j++)

    for(int k=0;k<m;k++)

    for(int t=0;t<2;t++){

        for(int s=0;s<10;s++){

            f0[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]=(f0[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]+f0[i][j][k][t][0])%Mod;

            f1[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]=(f1[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]+10LL*f1[i][j][k][t][0]+1LL*s*f0[i][j][k][t][0])%Mod;

            f2[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]=(f2[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]+100LL*f2[i][j][k][t][0]+20LL*s*f1[i][j][k][t][0]+1LL*s*s*f0[i][j][k][t][0])%Mod;

        }

        for(int s=0;s<a[i+1];s++){

            f0[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]=(f0[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]+f0[i][j][k][t][1])%Mod;

            f1[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]=(f1[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]+10LL*f1[i][j][k][t][1]+1LL*s*f0[i][j][k][t][1])%Mod;

            f2[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]=(f2[i+1][(j+s)%m][(k*10+s)%m][(s==m)||t][0]+100LL*f2[i][j][k][t][1]+20LL*s*f1[i][j][k][t][1]+1LL*s*s*f0[i][j][k][t][1])%Mod;

        }

        f0[i+1][(j+a[i+1])%m][(k*10+a[i+1])%m][(a[i+1]==m)||t][1]=(f0[i+1][(j+a[i+1])%m][(k*10+a[i+1])%m][(a[i+1]==m)||t][1]+f0[i][j][k][t][1])%Mod;

        f1[i+1][(j+a[i+1])%m][(k*10+a[i+1])%m][(a[i+1]==m)||t][1]=(f1[i+1][(j+a[i+1])%m][(k*10+a[i+1])%m][(a[i+1]==m)||t][1]+10LL*f1[i][j][k][t][1]+1LL*a[i+1]*f0[i][j][k][t][1])%Mod;

        f2[i+1][(j+a[i+1])%m][(k*10+a[i+1])%m][(a[i+1]==m)||t][1]=(f2[i+1][(j+a[i+1])%m][(k*10+a[i+1])%m][(a[i+1]==m)||t][1]+100LL*f2[i][j][k][t][1]+20LL*a[i+1]*f1[i][j][k][t][1]+1LL*a[i+1]*a[i+1]*f0[i][j][k][t][1])%Mod;

    }

    int ans=0;

    for(int i=0;i<m;i++)

        for(int j=0;j<m;j++)

            for(int k=0;k<=1;k++)

                ans=(ans+f2[n][i][j][1][k])%Mod;

    for(int i=0;i<m;i++)

        for(int j=0;j<=1;j++)

            ans=(ans+f2[n][0][i][0][j])%Mod;

    for(int i=1;i<m;i++)

        for(int j=0;j<=1;j++)

            ans=(ans+f2[n][i][0][0][j])%Mod;

    return ans;

}

int main(){

//  freopen("bachelor.in","r",stdin);

//  freopen("bachelor.out","w",stdout);

    int T;scanf("%d",&T);

    while(T--){

        scanf("%lld%lld%d",&l,&r,&m);

        printf("%d\n",(dp(r)-dp(l-1)+Mod)%Mod);

    }

    return 0;

}

mike