优美数

Description

如果一个数中只有少于三个数字是非零的，那么我们称这个数为优美数，我们定义这个优美数的优美程度为这个数所有数字相加的和。例如优美数有4，200000，10203，其中4的优美度是4，200000的优美度是2，10203的优美度是6. 数字4231，102306，7277420000，就不是啰。

现在问在【L，R】中，有多少个优美度为x的优美数。

Input

T组数据，T<=5e4. 第一行为组数T。接下来T行，每组输入L，R，x。1<=L <= R <= 3e18;

Output

每行输出一个对应的答案

Sample Input

4 1 1000 1 1024 1024 7 65536 65536 15 1 1000000000 20

Sample Output

4 1 0 3024

HINT

C++版本一

#include <algorithm>
#include  <iterator>
#include  <iostream>
#include   <cstring>
#include   <cstdlib>
#include   <iomanip>
#include    <bitset>
#include    <cctype>
#include    <cstdio>
#include    <string>
#include    <vector>
#include     <stack>
#include     <cmath>
#include     <queue>
#include      <list>
#include       <map>
#include       <set>
#include   <cassert>
using namespace std;


typedef long long ll;

            const int maxn = 3e6+9;
            int tot = 0;
            vector<ll>mp[30];
            int cnt(ll x){
                int res = 0;
                while(x>0){
                    res += x%10;
                    x/=10;
                }
                return res;
            }
            set<int>sss;
            void dfs(ll x,int cur,int num){
                if(cur>19||num > 3)return;

                if(num<=3){
                    int tmp = cnt(x);
                    mp[tmp].pb(x);
                    // tot++;
                    sss.insert(tmp);
                    // if(cnt(x) == 50)cout<<x<<endl;
                }
                for(int i=0;i<=9; i++){
                    if(i==0)dfs(x*10ll, cur+1,num);
                    else dfs(x*10ll + i, cur+1,num+1);
                }
            }
            int find1(ll x,int id){
                int le = 0,ri = mp[id].size() - 1;
                int res = ri+1;
                while(le <= ri){
                    int mid = (le + ri)>>1;
                    
                    if(mp[id][mid] < x){
                        le = mid+1;
                    }
                    else{
                        res = mid; ri = mid - 1;
                    }
                }

                return res;
            }
             int find2(ll x,int id){
                int le = 0,ri = mp[id].size() - 1;
                int res = 0;
                while(le <= ri){
                    int mid = (le + ri)>>1;
                    if(mp[id][mid] > x){
                        ri = mid - 1;
                    }
                    else {
                        res = mid;
                        le = mid + 1;
                    }
                }
                return res;
            }
int main(){

            // freopen("data.in","r", stdin);
            // freopen("output.out","w",stdout);
            for(int i=1; i<=9; i++)dfs(i,1,1);
            //tot = 720423
    
            for(int k : sss){//27次
                sort(mp[k].begin(),mp[k].end());
            }

            int t;scanf("%d", &t);
            while(t--){
                ll l,r;int x;
                scanf("%lld%lld%d", &l, &r, &x);
                if(x >= 28){
                    puts("0");
                }
                else if(l<r){
                        int t1 = find1(l,x);
                        int t2 = find2(r,x);
                        printf("%d\n",t2 - t1 + 1);
                }
                else if(l==r){
                        int t1 = lower_bound(mp[x].begin(),mp[x].end(),l) - mp[x].begin();
                        if(t1<mp[x].size() && mp[x][t1] == l)puts("1");
                        else puts("0");
                }
            }
           return 0;
}

C++版本二

#include <algorithm>
#include  <iterator>
#include  <iostream>
#include   <cstring>
#include   <cstdlib>
#include   <iomanip>
#include    <bitset>
#include    <cctype>
#include    <cstdio>
#include    <string>
#include    <vector>
#include     <stack>
#include     <cmath>
#include     <queue>
#include      <list>
#include       <map>
#include       <set>
#include   <cassert>
using namespace std;
#define se second
#define fi first
#define ll long long
#define Pii pair<int,int>
#define Pli pair<ll,int>
#define ull unsigned long long
#define pb push_back
const int N=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
using namespace std;
int a[30];
ll dp[20][30][4][30];
int k;
ll dfs(int pos,int now,int num,bool limit){
    if(num > 3) return 0;
    if(pos==-1) return now == k;
    if(!limit && dp[pos][now][num][k]!=-1) return dp[pos][now][num][k];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=up&&now+i<=k;++i){
       ans+=dfs(pos-1,now+i,num+(i!=0),limit&&i==a[pos]);
    }
    if(!limit) dp[pos][now][num][k]=ans;
    return ans;
}
ll solve(ll x){
    int pos=0;
    if(x==0)return 0;
    while(x){
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,0,1);
}
int main(){
//    freopen("data1.in", "r", stdin);
//    freopen("ac.out", "w", stdout);
    memset(dp,-1,sizeof(dp));

    int T;scanf("%d",&T);
    while(T--){
        ll l,r;
        scanf("%I64d%I64d%d",&l,&r,&k);
        if(k>27)printf("0\n");
        else printf("%I64d\n",solve(r)-solve(l-1));
    }

    return 0;
}