P2022 interesting numbers (binary & digit DP)

P2022 Interesting numbers ( Two points & digit dp)

It's numb .

Two points answer , Then use digits dp Calculation $[1,x]$ How many numbers in the dictionary order $<$$k$.

digit dp Open two arrays when $a,b$ save $x,k$.

Then there are conventional digits dp operation .

Note that if $dp$ Open the array to $lim,lead$ Every time $check$ All need to be initialized $dp$ by $-1$.

Because these two variables are related to $x$ of .

Otherwise, you can initialize only once .

in addition $w,w1$ The length is not necessarily the same , therefore $pos2$ May be reduced to $-1$. So let $w1$ The base number is $20$.

// Problem: P2022  Interesting numbers 
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2022
// Memory Limit: 125 MB
// Time Limit: 400 ms
// Date: 2022-07-05 13:23:31
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
ll f[20][40][2][2][2],n,m;
int a[20],w;
int b[40],w1;

ll dfs(int pos, int pos2, bool cmp, bool lim, bool lead) {
    
    if (pos == 0)
        return (cmp || pos2 > 20) && (!lead);
    if ( f[pos][pos2][cmp][lim][lead] != -1)
        return f[pos][pos2][cmp][lim][lead];
    ll tmp = 0, up = lim ? a[pos] : 9;
    for (int i = 0; i <= up; ++i) {
    
        bool nxcmp = !(lead && i == 0) && i < b[pos2];
        nxcmp |= cmp;
        if (!cmp && i > b[pos2])
            continue;
        tmp += dfs(pos - 1, pos2 - ((lead && i == 0) ? 0 : 1), nxcmp, lim && i == a[pos], lead && i == 0);
    }
    return    f[pos][pos2][cmp][lim][lead] = tmp;
}
ll check(ll n) {
    
    w = 0;memset(f, -1, sizeof (f));
    while (n)
        a[++w] = n % 10, n /= 10;
    //printf("w=%d\n",w);
    ll re = dfs(w, w1, false, true, true);
    return re;
}
int main()
{
    
    scanf("%lld%lld", &n, &m);
    w1 = 20;
    ll l = m > n ? m : n, r = 7e17, ans = 0;
    while (n)
        b[++w1] = n % 10, n /= 10;
    //printf("w1=%d\n",w1);
    for (; l <= r;) {
    
        ll mid = (l + r) >> 1, tmp = check(mid);
       // printf("%lld %lld\n",mid,tmp);
        if (tmp == m - 1) {
    
            ans = mid; r = mid - 1;
        }
        else if (tmp < m - 1) l = mid + 1;
        else r = mid - 1;
    }
    printf("%lld\n", ans);
}