Hướng dẫn giải

Đếm số có đúng ~n~ chữ số (chữ số đầu khác 0) có tổng chữ số bằng ~s~, lấy dư theo ~10^9 + 7~. Đây là bài quy hoạch động đếm theo số chữ số đã chọn và tổng hiện tại.

Sub 1: Vét cạn — ~O(10^n)~, dùng khi ~n \le 7~

Đệ quy chọn lần lượt từng chữ số (chữ số đầu từ 1 đến 9, các chữ số sau từ 0 đến 9), cắt nhánh khi tổng vượt quá ~s~, đến hết ~n~ chữ số thì đếm nếu tổng đúng bằng ~s~. Với ~n \le 7~ nhiều nhất cỡ ~9 \cdot 10^6~ số nên chạy kịp.

Sub 2: Quy hoạch động — ~O(n \cdot s \cdot 10)~

Gọi ~f[i][j]~ là số cách chọn ~i~ chữ số đầu có tổng ~j~. Khởi tạo ~f[1][c] = 1~ với ~c = 1 \ldots 9~ (chữ số đầu khác 0). Với ~i \ge 2~: ~f[i][j] = \sum_{c=0}^{9} f[i-1][j-c]~, lấy dư mỗi bước. Đáp số là ~f[n][s]~; khi ~s > 9n~ kết quả tự nhiên bằng 0. Tốn khoảng ~100 \cdot 1000 \cdot 10 = 10^6~ phép tính.

Lưu ý: máy chấm cục bộ không có dữ liệu thử của bài này, nên hai sub được kiểm tra bằng hai ví dụ trong đề và so sánh chéo kết quả sub 1 với sub 2 trên nhiều cặp ~(n, s)~ nhỏ, kết quả trùng nhau.

Chương trình hoàn chỉnh

Chương trình đọc ~n, s~; nếu ~n \le 7~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

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

const int MOD = 1000000007;
int n, s;

// Sub 1: vét cạn đệ quy chọn từng chữ số — ~O(10^n)~, dùng khi n <= 7
long long dem;
void tim(int vt, int tong) {
    if (vt == n) { if (tong == s) dem++; return; }
    for (int c = (vt == 0 ? 1 : 0); c <= 9; c++)
        if (tong + c <= s) tim(vt + 1, tong + c);
}
void sub1() {
    dem = 0;
    tim(0, 0);
    printf("%lld\n", dem % MOD);
}

// Sub 2: QHĐ f[i][j] = số cách chọn i chữ số đầu có tổng j — ~O(n * s * 10)~
long long f[105][1005];
void sub2() {
    for (int c = 1; c <= 9 && c <= s; c++) f[1][c] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= s; j++) {
            long long v = 0;
            for (int c = 0; c <= 9 && c <= j; c++) v += f[i - 1][j - c];
            f[i][j] = v % MOD;
        }
    printf("%lld\n", f[n][s] % MOD);
}

int main() {
    freopen("CNTNUM.INP", "r", stdin);
    freopen("CNTNUM.OUT", "w", stdout);
    scanf("%d %d", &n, &s);
    if (n <= 7) sub1();
    else sub2();
}