岩石谷 P4999 令人讨厌的数学作业问题解决方法
题目传送门
题目大意: 问 l l l ~ r r r 区间每个数的数字和。
题解
分明就是数位dp呀。
设 f [ i ] f[i] f[i] 表示 i i i 位的数的数字和。显然枚举一下每一位填什么数,然后再乘其他位置有多少种情况即可,除了最高位不能填 0 0 0,其他位都是可以的,所以特殊处理一下最高位即可。至于位数与 n n n 相同的,再分开处理一下就可以了。
代码如下:
#include <cstdio>
#include <cstring>
#define ll long long
#define mod 1000000007ll
ll n,m;
ll f[20],p[20];
void work()//dp
{
p[0]=1;
for(ll i=1;i<=18;i++)//p[i]表示10^i
p[i]=(p[i-1]*10)%mod;
f[0]=0;//f意义如上所述
for(int i=1;i<=18;i++)//枚举位数
{
for(int j=1;j<=9;j++)//枚举填什么数
{
f[i]=(f[i]+(ll)j*p[i-1]%mod)%mod;//把j填在最高位的情况
if(i>1)f[i]=(f[i]+(ll)(i-1)*j%mod*p[i-2]%mod*9ll%mod)%mod;
//把j填在2~i位的情况
}
}
}
int a[20],t;
ll solve(ll x)
{
if(x==0)return 0;
t=0;
while(x>0)a[++t]=x%10,x/=10;
ll ans=0,tot=a[t],sum=0;//tot记录前面已经搞过的位的数字和,结合下面代码即可理解
for(int i=1;i<t;i++)//位数比x的位数小的直接记录答案
sum=(sum+f[i])%mod;
ans=sum;
//处理位数与x相同的情况
if(t!=1)
for(int j=1;j<a[t];j++)//假如最高位比x的最高位小
ans=((ans+sum)%mod+(ll)j*p[t-1]%mod)%mod;
//再假设最高位与x的最高位相同,以同样的方法做后面的几位
for(int i=t-1;i>1;i--)
{
sum=(sum-f[i]+mod)%mod;
for(int j=0;j<a[i];j++)
ans=((ans+sum)%mod+(tot+j)*p[i-1]%mod)%mod;
tot+=a[i];
}
if(t==1)tot=0;//特殊处理一下第一位(即个位)
for(int i=0;i<=a[1];i++)
ans=((ans+tot)%mod+i)%mod;
return ans;
}
int main()
{
work();
int tt;
scanf("%d",&tt);
while(tt--)
{
scanf("%lld %lld",&n,&m);
printf("%lld\n",(solve(m)-solve(n-1)+mod)%mod);
}
}