# Bài 3
## **ĐỀ BÀI**

*Những dữ kiện trong đề bài và cách diễn đạt đều được viết lại so với đề gốc. Tụi mình rất mong nhận được phản hồi của các bạn nếu phát hiện sai sót.*

Một số nguyên dương $x$ được gọi là *S-digit* nếu như **tổng các chữ số** của $x$ là một số nguyên tố. Nhắc lại, số nguyên tố là số nguyên dương có duy nhất hai ước số phân biệt là $1$ và chính nó (số $1$ không phải số nguyên tố).

### Yêu cầu
Cho $Q$ truy vấn, mỗi truy vấn có dạng $l, r$ ($1 \leq l \leq r \leq 250$). Với mỗi truy vấn, đếm số lượng số *S-digit* có số lượng chữ số không nhỏ hơn $l$ và không lớn hơn $r$ (thuộc khoảng $[l, r]$). Kết quả in ra là phần dư trong phép chia của kết quả tìm được cho $10^9 + 7$.

### Input (Vào từ tệp "SDIGIT.INP")
- Dòng đầu tiên chứa số nguyên dương $Q$ ($1 \leq Q \leq 10$).
- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ và $r$ cách nhau bởi dấu cách, biểu diễn một truy vấn ($1 \leq l \leq r \leq 250$).

### Output (Xuất ra tệp "SDIGIT.OUT")
- Gồm $Q$ dòng, mỗi dòng xuất ra một số nguyên. Với truy vấn thứ $i$, xuất ra phần dư của phép chia giữa kết quả của truy vấn tương ứng và $10^9 + 7$ trên dòng $i$.

### Ví dụ

| SDIGIT.INP | SDIGIT.OUT |
| :------------------ | :--------- |
| 2 <br> 1 1 <br> 1 2 | 4 <br> 37 |

### Giải thích
Trong truy vấn đầu tiên ($l = 1, r = 1$), có $4$ số *S-digit* thỏa là $2, 3, 5, 7$.

### Ràng buộc
1. $80\%$ số test tương ứng với $80\%$ số điểm có $Q \leq 10$ và $l \leq r \leq 6$.
2. $20\%$ số test còn lại tương ứng với $20\%$ số điểm có $Q = 1$ và $l \leq r \leq 250$.

## **LỜI GIẢI**
### Subtask 1: $Q \leq 10$ và $l \leq r \leq 6$.
- Nhận thấy $l, r \leq 6$. $\Rightarrow$ Ta chỉ quan tâm các số có tối đa $6$ chữ số, tức là các số trong khoảng $[2, 10^6)$.
- Với mỗi truy vấn, ta duyệt qua tất cả các số có ít nhất $l$ chữ số và tối đa $r$ chữ số (từ $10^{l-1}$ đến $10^r - 1$). Với mỗi số $i$, ta tính tổng các chữ số của $i$ rồi kiểm tra liệu tổng đó có phải số nguyên tố hay không.
- Để tối ưu thời gian, kiểm tra số nguyên tố trong $O(1)$, ta có thể tạo và tính trước mảng ```bool prime[N]``` (với ```N``` là tổng lớn nhất có thể của các chữ số trong một số, có thể lấy ```N = 100```).

**Thời gian chạy:** $O(Q \times 10^6 \times r)$ (với $k$ là độ phức tạp để tính tổng các chữ số trong một số nguyên, $k$ là hằng số tương đối nhỏ).

### Subtask 2: $Q = 1$ và $l \leq r \leq 250$.
**Ý tưởng:** Biến đổi cách hiểu ***"tổng các chữ số trong một số có $n$ chữ số"*** thành ***"tổng các phần tử trong mảng $a$ độ dài $n$, $0 \leq a_i \leq 9$"***.

**Lưu ý:** Chữ số đầu tiên trong một số nguyên dương luôn phải khác $0$. Kết hợp với phần "ý tưởng" trên, đề bài sẽ được phát biểu lại thành:
***"Đếm số lượng mảng $a$ có ít nhất $l$ phần tử và tối đa $r$ phần tử ($0 \leq a_i \leq 9$ và $a_1 \neq 0$) sao cho tổng các phẩn tử trong mảng $a$ là số nguyên tố."***

Ta sẽ giải bài toán trên bằng thuật toán Quy hoạch động:
- Định nghĩa $dp[n][s]$ là số mảng $a$ khác nhau có độ dài $n$, sao cho tổng của mảng $a$ là $s$.
- Trường hợp cơ bản: $dp[0][0] = 1$
- **Tư duy:** Để tạo ra mảng $a$ có $n$ phần tử, ta sẽ đặt một phần tử thứ $n$ (gọi phần tử đó là $x$) vào mảng đã có sẵn $n - 1$ phần tử. Giả sử tổng của mảng $a$ sau khi thêm phần tử mới là $s$; khi đó, tổng của mảng $a'$ (mảng trước khi thêm) sẽ là $s - x$:

$a' = a_1 a_2 a_3 ... a_{n-1} = s - x$.
$a = a_1 a_2 a_3 ... a_{n-1} a_n = s$ (với $a_n = x$).

Ta thấy rằng, ta có tổng cộng $dp[n-1][s-x]$ cách để tạo ra mảng $a'$ có $n-1$ phần tử và tổng là $s-x$. Và sau khi đặt phần tử $x$ vào vị trí thứ $n$, mỗi cách tạo mảng $a'$ như thế sẽ tương ứng với thêm một cách tạo ra mảng $a$ có $n$ phần tử có tổng là $s$. Theo điều kiện đề bài, $x$ có thể nhận các giá trị từ $0$ đến $9$.
- **Công thức truy hồi:** Suy ra từ phần "Tư duy" trên, ta có:
- Nếu $n = 1$:
$$
dp[n][s] = \sum_{x = 1}^{9} dp[n - 1][s - x]
$$
- Nếu $n \neq 1$:
$$
dp[n][s] = \sum_{x = 0}^{9} dp[n - 1][s - x]
$$

Sau khi đã tính xong toàn bộ mảng $dp$, ta sẽ lần lượt duyệt mọi giá trị độ dài $i$ từ $l$ đến $r$, mọi giá trị tổng có thể $s$ ($s \leq 250 \times 9 \leq 2500$) từ $2$ đến xấp xỉ $2500$, nếu $s$ là số nguyên tố thì ```ans += dp[i][s]```.

Lưu ý, bài toán yêu cầu xuất kết quả tìm được $mod$ $10^9 + 7$, nên phần cài đặt cần xử lý phép $mod$ này trong công thức Quy hoạch động.

Độ phức tạp: $O(r \times Sum \times 10)$ với $Sum \approx 2500$.

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

const int N = 250, M = 3000, MOD = 1e9 + 7;

int q;
int tens[15];  // tens[i] = 10^i
bool prime[M + 5];
long long dp[N + 5][M + 5];

bool isPrime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

void init() {
    for (int i = 2; i <= M; i++) {
        prime[i] = isPrime(i);
    }
}

int s(int x) {
    int res = 0;
    while (x > 0) {
        res += x % 10;
        x /= 10;
    }
    return res;
}

void sub1() {
    tens[0] = 1;
    for (int i = 1; i <= 6; i++) tens[i] = tens[i - 1] * 10;

    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for (int j = tens[l - 1]; j < tens[r]; j++) {
            int sum_digits = s(j);
            if (prime[sum_digits]) ans++;
        }
        cout << ans << "\n";  // khong can ans %= mod vi trong sub1, ans < mod
    }
}

void sub2() {
    int l, r;
    cin >> l >> r;

    dp[0][0] = 1;
    for (int i = 1; i <= r; i++) {
        for (int x = 0; x <= 9; x++) {
            if (x == 0 && i == 1) continue;
            for (int s = x; s <= M; s++) {
                dp[i][s] += dp[i - 1][s - x];
                dp[i][s] %= MOD;
            }
        }
    }

    long long ans = 0;
    for (int s = 2; s <= M; s++) {
        if (!prime[s]) continue;

        for (int i = l; i <= r; i++) {
            ans += dp[i][s];
            ans %= MOD;
        }
    }

    cout << ans;
}

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

    init();

    cin >> q;
    if (q > 1)
        sub1();
    else
        sub2();
}