数位DP
思路
见: https://www.cnblogs.com/Laoli-2020/p/14049203.html
不能用pow这个函数,不然会有一个点过不了,咱也不清楚这个内置函数到底咋实现的,所以建议还是自己写一个pow
最后为什么要那样输出的原因见: https://www.luogu.com.cn/discuss/337496
总得来说我觉得这题很难…不应该只是个绿色的题目吧。。。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll f[21][10],l,r;
int T;
int getlen(ll x)//求位数
{
int n=0;
while(x)
{
n++;
x/=10;
}
return n;
}
int getfirst(ll x)//求最高位
{
while(x>=10)x/=10;
return x;
}
ll power(int x)//求10的x次方
{
long long an=1;
for(int i=1;i<=x;i++)an*=10;
return an;
}
ll getans(ll x)//这个是统计总和的函数,自己思考一下为啥要这样做
{
if(x==0)return 0;
ll xx=x,ans=0;
int len=getlen(x),first=getfirst(x);
for(int j=first-1;j>=0;j--)ans=(ans+f[len][j])%mod;
//统计整块
x-=first*power(len-1);
return (ans+1LL*first*(x+1)%mod+getans(x))%mod;
//统计零散小块
}
int main()
{
cin>>T;
for(int i=0;i<=9;i++)
f[1][i]=i;
for(int i=2;i<=19;i++)
{
for(int j=0;j<=9;j++)
f[i][0]=(f[i][0]+f[i-1][j])%mod;
for(int j=1;j<=9;j++)
f[i][j]=(f[i][0]+j*power(i-1))%mod;
}
while(T--)
{
cin>>l>>r;
cout<<(getans(r)-getans(l-1)+mod)%mod<<endl;
}
return 0;
}