Сколько несчастливых чисел в отрезке [a;b]?

Я не дам вам полного решения, но дам вам подсказку, которая должна указать вам правильное направление. Вам нужно применить некоторые математические знания (перестановки и комбинации) к этой задаче.

Предположим, вы хотите найти количество номеров несчастливый в [0, 12345). С некоторой математикой вы можете вычислить количество таких чисел в [0, 10000) за O (1). Затем вы можете вычислить количество таких чисел в [10000, 12000) за O (1). Тогда сделайте это для [12000, 12300). Теперь, если вы видите, куда мы идем...

Чтобы найти количество несчастливых чисел в [a, b], мы можем просто вычислить количество несчастливых чисел в [0, a) и количество несчастливых чисел в [0, b+1).

Примечание. На самом деле вам не нужно вычислять количество несчастливых чисел в [0, 10000) за O (1). Также достаточно найти способ вычислить количество несчастливых чисел в [0, 10000) от количества несчастливых чисел в [10000, 12000) за O(1).

Это можно легко решить за время O (log N) с помощью динамического программирования, известного как «dp on digits».

Во-первых, обратите внимание, что вместо вычисления несчастливых чисел в inertval [L,R] мы можем вместо этого определить некоторую функцию f(X) который вычисляет несчастливые числа в интервале [0,x], поэтому несчастливые числа в интервале [L,R] можно рассчитать как f(R) - f(L-1)

Создать функцию f() довольно просто, у нас есть состояние как dp[pos][ls][unlucky], где:

• pos - текущая цифра, которую мы пытаемся заполнить
• ls - просто флаг, который говорит, соответствует ли наш префикс пределу того, как высоко мы можем подняться
• unlucky - еще один флаг, говорящий, наш номер уже неудачный или нет

Затем мы можем сделать простое рекурсивное расширение по цифрам + запоминание.

Пример кода (С++ 11):

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll dp[51][2][2];
ll digits[51];
int amount_of_digits;

ll solve(ll pos, ll ls, ll unlucky)
{
    if (pos >= amount_of_digits)return unlucky;
    if (dp[pos][ls][unlucky]!=-1)return dp[pos][ls][unlucky];

    dp[pos][ls][unlucky]=0;

    for(int i=0; i<=(ls ? 9 : digits[pos]); i++) //next digit
        dp[pos][ls][unlucky]+=solve(pos+1,ls | (i<digits[pos]), unlucky | (i==5));

    return dp[pos][ls][unlucky];
}

ll f(ll x)
{
    string s = to_string(x);
    amount_of_digits = s.size();

    for(int i=0; i<s.size(); i++)
        digits[i] = s[i]-'0';

    memset(dp, -1, sizeof dp);
    return solve(0,0,0);
}

ll calc_interval(ll L, ll R)
{
    return f(R) - f(L-1);
}

int main()
{
    cout<<calc_interval(2,17);
}