题解 P4999 【烦人的数学作业】

# 数位$dp$一眼题 ------------ 其实看到这题后，脑子有很多思路的吧，而很巧的是，我刚做完[数字计数](https://www.luogu.org/problemnew/show/P2602) 我的思路瞬间被这道题框住，于是我想到我们可以把每一个数字出现的次数记录下来，乘上这个数字后就是答案了 举个例子，我们要求出$[l,r]$区间的数字和 那么我们只需要求出$[1,r]$这个区间所有数字和减去$[1,l-1]$区间所有数字和 那么怎么求数字和呢，假如我们要求$[1,r]$数字和，我们可以统计一下$1$~$9$每个数字出现的次数， 然后分别乘上$1$~$9$ 那么这个题目就转化为了上面数字计数了 ### 注意别爆了$long\ long$ 接下来是美滋滋的代码时间~~~ ~~~cpp #include<iostream> #include<cstdio> #include<cstring> #define N 25 #define int long long #define ll long long #define mod 1000000007 using namespace std; ll l,r,T,ans; int val[N]; ll f[N][N]; ll Dfs(int pos,bool lead,bool limit,int k,int sum) { if(!pos) return sum; if(!limit&&!lead&&f[pos][sum]!=-1) return f[pos][sum]; int maxn=limit?val[pos]:9; ll ans=0; for(int i=0;i<=maxn;++i) { if(lead&&!i) ans+=Dfs(pos-1,1,limit&&(i==maxn),k,sum); else ans+=Dfs(pos-1,0,limit&&(i==maxn),k,sum+(i==k)); } if(!limit&&!lead) f[pos][sum]=ans; return ans; } ll Get(int x,int k) { memset(f,-1,sizeof(f)); int len=0; while(x) { val[++len]=x%10; x/=10; } return Dfs(len,1,1,k,0); } signed main() { scanf("%lld",&T); while(T--) { ans=0; scanf("%lld%lld",&l,&r); for(int i=1;i<=9;++i) (ans+=((((Get(r,i)-Get(l-1,i)+mod)%mod)*i)%mod+mod)%mod)%=mod; printf("%lld\n",(ans+mod)%mod); } return 0; } ~~~