Cf1036c class numbers solution

CF1036C Classy Numbers Answer key

Topic link ：CF1036C Classy Numbers

The question ： Define a number as “ Good number ”, If and only if its decimal representation does not exceed $3$ A digital $1\sim 9$

for instance ：$4,200000,10203$ yes “ Good number ”, However $4231,102306,7277420000$ No

Given $[l,r]$, Ask how many $x$ bring $l\le x\le r$, And $x$ yes “ Good number ”

Altogether $T(1\le T\le 10^4)$ Group data , For each inquiry , Output an integer on a line to represent the answer

$1\le l_i\le r_i\le 10^{18}$

General figures dp It can be used to solve ${\sum }_{i=l}^{r}f(i)$ The problem of ,

among $f(i)$ As with the $i$ A function or determinant related to the digits of

This question is slightly distorted , Then we will naturally record the occurrence of figures

set up $f_{i,j}$ It means full $i$ digit , Yes $j$ A non $0$ position

Using memory search , See the code for details.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
int num[25],f[25][5];
// u Indicates the current number of digits ,st Represents the current j,limit Indicates whether there is a high limit 
int dfs(int u,int st,bool limit)
{
    
    if(!u)return 1;
    if(!limit&&f[u][st]!=INF)
        return f[u][st]; //  Memorize 
    int up=limit?num[u]:9,ans=0;
    for(int i=0; i<=up; i++)
    {
    
        if(!i)ans+=dfs(u-1,st,limit&&num[u]==i);
        else if(st!=3)ans+=dfs(u-1,st+1,limit&&num[u]==i);
    }
    if(!limit) f[u][st]=ans; //  Just record what has no upper limit 
    return ans;
}
int solve(int x)
{
    
    int len=0;
    while(x>0)
    {
    
        num[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,1);
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f,0x3f,sizeof(f));
    int Q;cin >> Q;
    while(Q--)
    {
    
        int l,r;
        cin >> l >> r;
        cout << solve(r)-solve(l-1) << '\n';
    }
    return 0;
}

reference

[1] https://www.luogu.com.cn/blog/rated/solution-cf1036c

Reprint please explain the source