\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• Truy vấn \(V = 1\): Tính tổng vạch led bật mỗi chữ số từ số \(n\)

Tiền xử lí \(10\) chữ số \(0..9\) xem nó cần bao nhiêu vạch led bật

• Truy vấn \(V = 2\): Với mỗi số \(x > n\) có cùng độ dài với \(n\). Tăng biến đếm nếu \(x\) có chứa các vạch led \(n\)

Ta có thể thử xây từng chữ số cho \(x\), từ đó đưa ta đến thuật quy hoạch động chữ số

\(\color{goldenrod}{\text{Tiếp cận truy vấn 1}}\)

• Gọi \(csl_x\) là số lượng đèn led cần bật để hiển thị số \(x\) (\(x = 0 \rightarrow 9\))

$csl[] = $ {\(6, 2, 5, 5, 4, 5, 6, 3, 7, 6\)}

• Kết quả bài toán là \(res = \underset{x \in n}{\Sigma}(csl_x)\) (\(x\) là các chữ số trong \(n\))

\(\color{goldenrod}{\text{Tiếp cận truy vấn 2 đệ quy}}\)

• Thử xây từng chữ số với hàm đệ quy magic(int index, bool isGreater)

Với \(index\) là vị trí các chữ số của \(n\) từ trái sang phải

Với \(isGreater\) là biến kiểm tra xem số hiện tại lớn hơn \(n\) chưa

Ta thử xây chữ số tiếp theo là chữ số có chứa các vạch led bật sẵn

• Ta có thể tiền xử lí xem với mỗi chữ số \(d = 0..9\) thì có những số \(nextd\) nào có vạch led \(d\) bật, tức những cách thỏa mãn

Nếu số hiện tại đã lớn hơn \(n\), thì mình có thể chọn mọi số \(nextd\) <=> \(lower_limit = 0\)

Nếu số hiện tại chưa lớn hơn \(n\), thì mình chỉ có thể chọn mọi số \(nextd ≥ d\) <=> \(lower_limit = d\)

Nếu số hiện tại đã lớn hơn \(n\) hoặc \(nextd > d\) thì \(isGreater = true\) (khởi tạo là False nhé)

Sau đó ta đệ quy chữ số tiếp theo: \(res = res + magic(index + 1, isGreater || (nextd > lower_limit))\)

\(\color{goldenrod}{\text{Tiếp cận truy vấn 2 vòng lặp}}\)

• Ta tính tích của (tổng số cách chọn tại \(i\)) - (số cách chọn số bé hơn \(n\) tại \(i\))

Duyệt \(i\) từ trái sang phải

Gọi \(ctw = count_total_ways\) là số cách chọn chữ số tại vị trí \(i\)

Gọi \(clw = count_less_ways\) là số cách chọn chữ số bé hơn tại vị trí \(i\)

Gọi \(res\) là tổng số cách chọn trước đó

Dựa vào đó ta tính tổng số cách chọn bây giờ

• Ta có thể tiền xử lí xem với mỗi chữ số \(d = 0..9\) thì số cách chọn \(ctw[d]\) và \(clw[d]\) là gì

Có \(ctw[d]\) là số lượng số \(x\) thỏa \(x\) chứa các vạch led \(d\) bật

Có \(clw[d]\) là số lượng số \(x < d\) thỏa \(x\) chứa các vạch led \(d\) bật

Từ đó suy ra công thức toán học \(res = res * ctw[d] - clw[d]\)

\(\color{purple}{\text{Độ phức tạp}}\)

• Truy vấn 1 mất \(O(log_{10}n)\)

• Truy vấn 2 mất \(O(log_{10}n)\) với hằng số \(O(1), O(2 \times 7), O(10 \times 10), \dots\) tùy cách cài

\(\color{green}{\text{Code tham khảo }}\): Quy hoạch động chữ số, Đồ thị đỉnh kề

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(log_{10}n)\ \color{purple}{\text{thời gian}}\ ||\ O(log_{10}n)\ \color{purple}{\text{bộ nhớ}}}}\)

C++

/// Tiền xử lí các vạch led bật
vector<int> cntled = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
void solve1()
{
    /// Biểu diễn số dưới dạng xâu
    string s;
    cin >> s;

    /// Kết quả là tổng số lượng vạch led bật
    int res = 0;
    for (char c : s)
        res += cntled[c - '0'];

    cout << res;
}

/// Tiền xử lí
/// vector thứ n biểu diễn tất cả các đèn led mà các vạch led có trong n được bật
vector<vector<int> > G = {
    {0, 8},                 /// [0]
    {0, 1, 3, 4, 7, 8, 9},  /// [1]
    {2, 8},                 /// [2]
    {3, 8, 9},              /// [3]
    {4, 8, 9},              /// [4]
    {5, 6, 8, 9},           /// [5]
    {6, 8},                 /// [6]
    {0, 3, 7, 8, 9},        /// [7]
    {8},                    /// [8]
    {8, 9},                 /// [9]
};

int n;                  /// Độ dài của số nhận vào
vector<int> v;          /// vector chứa các chữ số
vector<vector<ll> > f;  /// vector 2 chiều quy hoạch động
/// hàm magic(i, ign)
/// tại vị trí (i) của số biểu diễn bởi vector (v)
/// đếm số cách mà xây dựng được số có (ign) = true
ll magic(int i = 0, bool ign = false) /// O(n * 2 * 7)
{
    /// Nếu đã duyệt hết vector
    if (i >= n) return ign;

    /// Dùng con trỏ để tiện tính toán
    ll &res = f[i][ign];
    if (res != -1) return res; /// Nếu đã được tính trước đó
    else res = 0;              /// Ngược lại thì reset giá trị

    /// Chúng ta chỉ đếm các số lớn hơn
    int lim = ign ? 0 : v[i];
    for (int d : G[v[i]])
        if (d >= lim)
            res += magic(i + 1, ign || (d > lim));

    /// Đừng quên trả về kết quả :D
    return res;
}

void solve2()
{
    /// Biểu diễn số dưới dạng xâu
    string s;
    cin >> s;

    /// Dùng vector (v) độ dài (n) để lưu trữ các chữ số
    n = s.size();
    for (char c : s) v.pb(c - '0');

    /// Khởi tạo -1 tức là chưa được tính trước đó
    f.assign(n + 1, vector<ll>(2, -1));
    cout << magic();
}

\(\color{green}{\text{Code tham khảo }}\): Quy hoạch động chữ số, Đồ thị ma trận

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(log_{10}n)\ \color{purple}{\text{thời gian}}\ ||\ O(log_{10}n)\ \color{purple}{\text{bộ nhớ}}}}\)

/// Tiền xử lí các vạch led bật
vector<int> cntled = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
void solve1()
{
    ll n = readLong();
    int res = 0;       /// Kết quả là tổng số lượng vạch led bật
    do res += cntled[n % 10]; while (n /= 10);
    cout << res;
}


/// Tiền xử lí
/// bit thứ (i) của vector thứ (n) biểu diễn có thể chuyển đổi từ (led-i) sang (led-n) hay không
vector<vector<bool> > G = {
    {1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, /// [0] - 0, 8
    {1, 1, 0, 1, 1, 0, 0, 1, 1, 1}, /// [1] - 0, 1, 3, 4, 7, 8, 9
    {0, 0, 1, 0, 0, 0, 0, 0, 1, 0}, /// [2] - 2, 8
    {0, 0, 0, 1, 0, 0, 0, 0, 1, 1}, /// [3] - 3, 8, 9
    {0, 0, 0, 0, 1, 0, 0, 0, 1, 1}, /// [4] - 4, 8, 9
    {0, 0, 0, 0, 0, 1, 1, 0, 1, 1}, /// [5] - 5, 6, 8, 9
    {0, 0, 0, 0, 0, 0, 1, 0, 1, 0}, /// [6] - 6, 8
    {1, 0, 0, 1, 0, 0, 0, 1, 1, 1}, /// [7] - 0, 3, 7, 8, 9
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, /// [8] - 8
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 1}, /// [9] - 8, 9
};

int n;                  /// Độ dài của số nhận vào
vector<int> v;          /// vector chứa các chữ số
vector<vector<ll> > f;  /// vector 2 chiều quy hoạch động
/// hàm magic(i, ign)
/// tại vị trí (i) của số biểu diễn bởi vector (v)
/// đếm số cách mà xây dựng được số có (ign) = true
ll magic(int i = 0, int ign = false) /// O(n * 2 * 9)
{
    /// Nếu đã duyệt hết vector
    if (i >= n) return ign;

    /// Dùng con trỏ để tiện tính toán
    ll &res = f[i][ign];
    if (res != -1) return res; /// Nếu đã được tính trước đó
    else res = 0;              /// Ngược lại thì reset giá trị

    /// Chúng ta chỉ chọn những chữ số có thể chuyển đổi được
    int lim = ign ? 0 : v[i];
    for (int d = 9; d >= lim; --d)
        if (G[v[i]][d] == true)
            res += magic(i + 1, ign || (d > lim));

    /// Đừng quên trả về kết quả :D
    return res;
}

void solve2()
{
    /// Biểu diễn số dưới dạng xâu
    string s;
    cin >> s;

    /// Dùng vector (v) độ dài (n) để lưu trữ các chữ số
    n = s.size();
    for (char c : s) v.pb(c - '0');

    /// Khởi tạo -1 tức là chưa được tính trước đó
    f.assign(n + 1, vector<ll>(2, -1));
    cout << magic();
}

\(\color{green}{\text{Code tham khảo }}\): Quy hoạch động chữ số, Xử lí trực tiếp

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(log_{10}n)\ \color{purple}{\text{thời gian}}\ ||\ O(1)\ \color{purple}{\text{bộ nhớ}}}}\)

             ///   0  1  2  3  4  5  6  7  8  9
vector<int> csl = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; /// Đếm số vạch led bật
vector<int> ctw = {2, 7, 2, 3, 3, 4, 2, 5, 1, 2}; /// Số cách chọn chữ số tại vị trí i
vector<int> clw = {0, 1, 0, 0, 0, 0, 0, 2, 0, 1}; /// Số cách chọn chữ số bé hơn tại vị trí i
inline bool isDig(char c) { return '0' <= c && c <= '9'; } /// isDigit(char) ?
void solve1() /// O(log10 n)
{
    char c;
    while (c = getchar(), !isDig(c)); /// Bỏ các kí tự không phải chữ số

    int res = 0;
    do res += csl[c - '0']; 
    while (isDig(c = getchar())); /// Nhận chữ số (c) tiếp theo

    cout << res;
}

void solve2() /// O(log10 n)
{
    char c;
    while (c = getchar(), !isDig(c)); /// Bỏ các kí tự không phải chữ số

    ll res = 1;
    do res = res * ctw[c - '0'] - clw[c - '0']; 
    while (isDig(c = getchar()));  /// Nhận chữ số (c) tiếp theo

    cout << res - 1; /// Bỏ qua trường hợp bằng nhau
}