数位 DP

直接打上去数位 DP。时间复杂度：$O(\log l + \log r)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll l,r,m,adds;
ll a[10],dp[10][50];
inline ll dfs(const ll &idx,const ll &tag,const bool &limit){
    if(idx<=0) return tag==m;
    if(!limit&&~dp[idx][tag]) return dp[idx][tag];
    ll res=0,maxx=limit?a[idx]:9;
    for(ll i=0;i<=maxx;i++) res+=dfs(idx-1,tag+i,limit&&i==maxx);
    if(!limit) dp[idx][tag]=res;
    return res;
}
inline ll calc(ll x){
    if(x<=0) return 0;
    adds=0;
    while(x){
        a[++adds]=x%10;
        x/=10;
    }
    return dfs(adds,0,true);
}
int main(){
    memset(dp,-1,sizeof(dp));
    cin>>l>>r>>m;
    cout<<calc(r)-calc(l-1);
    return 0;
}