Tóm tắt đề bài

Cho hai số nguyên dương \(L\) và \(R\) có độ dài lên đến \(10000\) chữ số. Hãy đếm số lượng số nguyên \(x \in [L, R]\) thỏa mãn đồng thời hai điều kiện:

1. \(x\) chia hết cho \(19\).
2. Trong biểu diễn thập phân của \(x\), không có bất kỳ hai chữ số nào (không nhất thiết phải kề nhau) có tổng chia hết cho \(3\).

Kết quả cần được lấy dư cho \(10^9 + 7\).

Phân tích

1. Điều kiện về tổng hai chữ số chia hết cho 3

Xét các chữ số từ \(0\) đến \(9\) theo số dư khi chia cho \(3\):

• Nhóm dư 0: \(\{0, 3, 6, 9\}\)
• Nhóm dư 1: \(\{1, 4, 7\}\)
• Nhóm dư 2: \(\{2, 5, 8\}\)

Để tổng của hai chữ số bất kỳ \(a\) và \(b\) không chia hết cho \(3\), ta có các ràng buộc sau:

• Không thể có hai chữ số cùng thuộc nhóm dư 0 (vì \(0+0 \equiv 0 \pmod 3\)). Do đó, số \(x\) chỉ có thể chứa tối đa một chữ số thuộc nhóm \(\{0, 3, 6, 9\}\).
• Không thể có một chữ số dư 1 và một chữ số dư 2 cùng xuất hiện (vì \(1+2 \equiv 0 \pmod 3\)). Do đó, nếu \(x\) đã chứa một chữ số thuộc nhóm \(\{1, 4, 7\}\) thì không được phép chứa chữ số nào thuộc nhóm \(\{2, 5, 8\}\), và ngược lại.

Kết luận: Tập các chữ số xuất hiện trong \(x\) chỉ có thể là con tập của một trong các bộ sau:

• Bộ 1: Tối đa một số từ \(\{0, 3, 6, 9\}\) và bất kỳ số lượng số nào từ \(\{1, 4, 7\}\).
• Bộ 2: Tối đa một số từ \(\{0, 3, 6, 9\}\) và bất kỳ số lượng số nào từ \(\{2, 5, 8\}\).

2. Ràng buộc về bài toán

• Số lượng chữ số cực lớn (\(10^4\)) gợi ý sử dụng Quy hoạch động chữ số (Digit DP).
• Điều kiện chia hết cho \(19\) yêu cầu ta lưu trạng thái số dư khi chia cho \(19\).
• \(T\) lớn (\(10^5\)) nhưng tổng độ dài \(R\) không quá lớn ở các subtask đầu, tuy nhiên với ràng buộc gốc, ta cần một cách tiếp cận tối ưu hóa trạng thái DP để dùng chung cho nhiều testcase.

Hướng giải quyết

Trạng thái Quy hoạch động

Ta định nghĩa hàm \(dp(i, r, s)\) là số cách chọn các chữ số cho \(i\) vị trí còn lại sao cho:

• Số dư hiện tại khi chia cho \(19\) là \(r\).
• Trạng thái các chữ số đã chọn trước đó là \(s\).

Để tối ưu trạng thái \(s\), ta nhận thấy điều kiện "không có hai chữ số nào có tổng chia hết cho 3" có thể được biểu diễn qua việc đã dùng chữ số dư \(0, 1, 2\) hay chưa:

• \(s\) cần lưu trữ:
  • Đã có chữ số dư 0 nào chưa? (1 bit)
  • Đã có chữ số dư 1 nào chưa? (1 bit)
  • Đã có chữ số dư 2 nào chưa? (1 bit)
• Tuy nhiên, nếu đã có dư 1 thì không được có dư 2. Nếu đã có dư 0 thì không được thêm dư 0 nữa.
• Trạng thái \(s\) có thể gói gọn trong 3 bit (từ 0 đến 7) đại diện cho việc đã xuất hiện chữ số thuộc nhóm dư \(0, 1, 2\).

Chi tiết trạng thái và chuyển trạng thái

Khi xét một chữ số \(j\) định điền vào vị trí hiện tại:

• Gọi \(rem = j \pmod 3\).
• Nếu \(rem = 0\): Chỉ được điền nếu trong \(s\) chưa có chữ số dư 0.
• Nếu \(rem = 1\): Chỉ được điền nếu trong \(s\) chưa có chữ số dư 2.
• Nếu \(rem = 2\): Chỉ được điền nếu trong \(s\) chưa có chữ số dư 1.
• Lưu ý về số 0 ở đầu (leading zeros): Chữ số 0 chỉ được tính là "đã xuất hiện" nếu nó không phải là số 0 vô nghĩa ở đầu.

Tính toán cho đoạn \([L, R]\)

Số lượng số trong \([L, R]\) bằng \(count(R) - count(L-1)\).

• Để tính \(count(R)\), ta dùng kỹ thuật duyệt từng chữ số của \(R\) từ trái sang phải, tại mỗi vị trí thử các chữ số nhỏ hơn chữ số tương ứng của \(R\) và cộng kết quả từ mảng DP đã tính trước.
• Với \(L-1\), do \(L\) rất lớn, ta có thể thực hiện trừ 1 trên chuỗi hoặc tính \(count(R) - count(L)\) rồi kiểm tra xem \(L\) có thỏa mãn điều kiện đề bài hay không. Trong code tham khảo, ta thực hiện tăng \(R\) lên 1 đơn vị và tính \(count(R_{mới}) - count(L)\).

Độ phức tạp

• Tiền xử lý DP: \(O(N \times 19 \times 8 \times 10)\) với \(N = 10000\).
• Mỗi testcase: \(O(N \times 10)\).
• Tổng cộng: \(O(N \times 19 \times 80 + T \times N)\). Tuy nhiên, nhờ việc ghi nhớ (memoization) và cách duyệt, chương trình sẽ chạy đủ nhanh trong thời gian cho phép.

Code tham khảo

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

const int mod = 1000000007;
const int nmax = 10001;

// f[vị trí][số dư cho 19][trạng thái các nhóm dư 0, 1, 2 đã dùng]
int f[nmax][19][8];

// Hàm DP tính số lượng cách điền i chữ số tiếp theo
int dp(int i, int r, int s) {
    if (i == -1) return r == 0; // Nếu hết chữ số, kiểm tra chia hết cho 19
    int &ans = f[i][r][s];
    if (ans != -1) return ans;

    long long current_ans = 0;
    for (int j = 0; j < 10; ++j) {
        int rem = j % 3;
        bool can_place = true;

        // Kiểm tra điều kiện tổng chia hết cho 3
        if (rem == 0 && (s & 1)) can_place = false; // Đã có dư 0, không được thêm dư 0
        if (rem == 1 && (s & 4)) can_place = false; // Đã có dư 2, không được thêm dư 1
        if (rem == 2 && (s & 2)) can_place = false; // Đã có dư 1, không được thêm dư 2

        if (can_place) {
            int next_s = s;
            // Nếu không phải số 0 ở đầu hoặc đã bắt đầu số, cập nhật trạng thái
            if (!(j == 0 && s == 0)) {
                next_s |= (1 << rem);
            }
            current_ans = (current_ans + dp(i - 1, (r * 10 + j) % 19, next_s)) % mod;
        }
    }
    return ans = current_ans;
}

// Hàm đếm số lượng số thỏa mãn từ 1 đến S
int count_valid(string S) {
    int n = S.size();
    long long ans = 0;
    int current_r = 0;
    int current_s = 0;

    for (int i = 0; i < n; ++i) {
        int limit = S[i] - '0';
        for (int j = 0; j < limit; ++j) {
            int rem = j % 3;
            bool can_place = true;
            if (rem == 0 && (current_s & 1)) can_place = false;
            if (rem == 1 && (current_s & 4)) can_place = false;
            if (rem == 2 && (current_s & 2)) can_place = false;

            if (can_place) {
                int next_s = current_s;
                if (!(j == 0 && current_s == 0)) next_s |= (1 << rem);
                ans = (ans + dp(n - 1 - i, (current_r * 10 + j) % 19, next_s)) % mod;
            }
        }

        // Cập nhật trạng thái cho chữ số hiện tại của S để xét vị trí tiếp theo
        int rem = limit % 3;
        if ((rem == 0 && (current_s & 1)) || (rem == 1 && (current_s & 4)) || (rem == 2 && (current_s & 2))) {
            return ans; // Không thể khớp tiếp với tiền tố của S
        }
        if (!(limit == 0 && current_s == 0)) current_s |= (1 << rem);
        current_r = (current_r * 10 + limit) % 19;
    }
    return ans;
}

// Hàm cộng 1 vào số lớn dưới dạng chuỗi
void increment(string &R) {
    int n = R.size();
    for (int i = n - 1; i >= 0; --i) {
        if (R[i] < '9') {
            R[i]++;
            for (int j = i + 1; j < n; ++j) R[j] = '0';
            return;
        }
    }
    R = "1" + string(n, '0');
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(f, -1, sizeof(f));
    int T;
    cin >> T;
    while (T--) {
        string L, R;
        cin >> L >> R;
        increment(R); // Tính trên nửa khoảng [L, R+1)
        int ans = (count_valid(R) - count_valid(L) + mod) % mod;
        cout << ans << "\n";
    }
    return 0;
}