Description

快要到七夕了,又到了交(nue)往(gou)的季节。

恶梦坐在教室里,作为一个纯屌丝的他当然不会关心要送什么礼物给女生,然而他的前桌yves却在忙碌着各种各样的的短信。

恶梦注意到yves发短信给的电话号码似乎都满足着特别的性质,难道yves的"好朋友"是满足正态分布的？

由于yves有着自己最喜欢的数字a,2 <= a <= 9

恶梦从这里入手,发现了一些端倪。

假设yves发的电话号码是一个十进制数字S

恶梦发现S会满足以下三个性质中的一个

1. S是a的倍数。

2. S在十进制表示下的各项数字加起来是a的倍数。

3. S的某一位是a

比如说当a = 7时,21,16,17这三个数字都是会被yves发短信的,他们分别满足1,2,3性质。

恶梦很担心所有的女同学都被yves抢走了,但他一下子又数不过来那些同学没有被yves抢走,所以他把这个问题交给了你。

他会给你两个自然数L,R,以及yves最喜欢的数字a,

他并不希望你告诉他在[L,R]中有多少个同学没有被抢走,而希望你告诉他这些数字的平方和。

比如说3,7是合法的,那么你应该输出3^2 + 7^2 = 58这个数。

当然,由于答案可能很大,你只需要将答案对10^9 + 7取模即可。

 

Input

输入的第一行包括一个正整数T,表示总共有T组询问。

接下来有T行,每行三个整数L,R,A。

Output

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

 

Sample Input

3 2 20 6 3 203 7 11 771 2

Sample Output

1884 1593269 32817226

 

Data Constraint

对于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

 

题解

• 题目大意：给定一个区间，问区间内不满足以上所有条件的数的平方和
• 显然数位DP，设f[i][j][k][l]为当前枚举到第i位(从高到低)，前i位是否与R的前i位相同，当前的数对A取模的余数为k，当前的数位和对A取模的余数为l的方案数
• 再设s[i][j][k][l]为这些数的和，g[i][j][k][l]为这些数的平方和
• 转移也挺简单的，我们现有状态为(i, same, mo, sum)，然后枚举一个当前位置选的数ch
• 首先ch不能等于A，而且当same=1时，当前位不能大于R的当前位
• 然后就直接转移就好了，答案就是∑g[1][same][mo][sum]

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define ll long long 5 using namespace std; 6 const ll MO=1e9+7; 7 ll n,m,ans,l,r,a,f[40][2][10][10],g[40][2][10][10],s[40][2][10][10],K[40]; 8 ll calc(ll x) 9 {10     ll p=x,tot=0; memset(K,0,sizeof(K)),memset(f,0,sizeof(f)),memset(g,0,sizeof(g)),memset(s,0,sizeof(s));11     while (p) K[++tot]=p%10,p/=10;12     f[tot+1][1][0][0]=1;13     for (ll i=tot;i>=1;i--)14         for (ll j=0;j<=1;j++)15             for (ll mo=0;mo<=a-1;mo++)16                 for (ll sum=0;sum<=a-1;sum++)17                     if (f[i+1][j][mo][sum])18                         for (ll ch=0;ch<=9;ch++)19                             if (ch!=a&&(!(j&&ch>K[i])))20                             {21                                 ll b=(j&&ch==K[i]),c=(mo*10+ch)%a,d=(sum+ch)%a;22                                 f[i][b][c][d]=(f[i][b][c][d]+f[i+1][j][mo][sum])%MO;23                                 s[i][b][c][d]=(s[i][b][c][d]+10ll*s[i+1][j][mo][sum]%MO+f[i+1][j][mo][sum]*ch%MO)%MO;24                                 g[i][b][c][d]=(g[i][b][c][d]+100ll*g[i+1][j][mo][sum]%MO+20ll*ch*s[i+1][j][mo][sum]%MO+ch*ch*f[i+1][j][mo][sum]%MO)%MO;25                             }26     ll ans=0;27     for (ll j=0;j<=1;j++) for (ll mo=1;mo<=a-1;mo++) for (ll sum=1;sum<=a-1;sum++) (ans+=g[1][j][mo][sum])%=MO;28     return ans;29 }30 int main()31 {32     scanf("%lld",&n);33     while (n--)34     {35         scanf("%lld%lld%lld",&l,&r,&a);36         printf("%lld\n",(calc(r)-calc(l-1)+MO)%MO);37     }38 }