Digital statistics DP AcWing 338. Counting problem

Original link

AcWing 338. Counting problem

Ideas

For numbers n Each number has a number x Have a classified discussion
Fourth place here d For example

See code for details

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 15;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
int pow(int x){
    int res=1;
    while(x--){
        res*=10;
    }
    return res;
}
//  Get array a The first r Bit to bit l Digit number 
int get(vector<int> a, int l, int r){
    int res=0;
    Rep(i, l, r){
        res=res*10+a[i];
    }
    return res;
}
// 1 to n in x Number of occurrences 
int cnt(int n, int x){
    if(!n){
        return 0;
    }
    else{
        vector<int> a;
        while(n){
            a.push_back(n%10);
            n/=10;
        }
        int res=0;
        n=a.size();
        //  if x by 0 n-2->0  Because the highest bit cannot be 0,  So we should start from n-2 Start 
        //  if x Not 0 n-1->0
        Rep(i, n-1-!x, 0){
            //  front i digit ( namely abc) Composition less than n In the numbers x Number of occurrences 
            if(i<n-1){
                res+=(get(a, n-1, i+1))*pow(i);
                //  Before removal i The number of digits is zero 
                if(!x){
                    res-=pow(i);
                }
            }
            //  The first i Bit after ( namely efg) Less than n In the numbers x Number of occurrences 
            if(a[i]==x){
                res+=get(a, i-1, 0)+1;
            }else if(a[i]>x){//  The first i The number of all digits after the digit 
                res+=pow(i);
            }
        }
        return res;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a, b;
    while(a=read(), b=read(), a){
        if(a>b){
            swap(a, b);
        }
        rep(i, 0, 10){
        	// a To b in i Number of entries 
            printf("%lld ", cnt(b, i)-cnt(a-1, i));
        }
        puts("");
    }
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support