Subtask 1: ~\lfloor \frac{m}{a_1} \rfloor~

Subtask 2: Xét bất phương trình ~ax + by \leq m~; số nghiệm nguyên không âm của bất phương trình là:

Vì ~b \leq 10~ nên trong 10 số ~a \times 1~, ~a \times 2~, ~\ldots~, ~a \times 10~ có ít nhất hai số đồng dư với nhau theo modulo ~b~

Với mỗi số dư ~0~, ~1~, ~2~, ~\ldots~, ~b - 1~; ta xem nó đóng góp bao nhiêu cho đáp án:

Nếu cố định số dư ~r~, ta tìm được số ~m'~ lớn nhất mà ~m' \leq m~ và ~m' \equiv r \pmod{b}~; số lượng đóng góp của các ~x \times a \equiv r \pmod{b}~ là ~\frac{m - x \times a}{b} + 1~. Ta tách riêng ~m'~ và ~x \times a~ và dùng công thức cho từng phần

Subtask 3: Bài toán sẽ tương đương với đếm số nghiệm không âm của bất phương trình: ~a_1 \times x_1 + a_2 \times x_2 + \ldots + a_n \times x_n~ ~\leq m - a_1 - a_2 - \ldots - a_n~

Lúc này bài toán chính là bài toán CSES - Coin Combinations II

Subtask 4: Sử dụng dp digit, ta xây dựng từng đơn vị cho tất cả các biến như code bên dưới

Code mẫu

#include <iostream>
#include <cstdio>
#include <algorithm>
#define task ""
using namespace std;
using ll = long long;
using ld = long double;

const int N = 5e2 + 5;
const ll mod = 1e9 + 7;
int a[N];
string n;
int m, k;
ll dp[N][2][12][2005];

void Read()
{
    cin >> k >> m;

    for (int i = 1; i <= k; ++i) {
        cin >> a[i];
        m -= a[i];
    }

    if(m < 0) {
        cout << 0;
        exit(0);
    }

    n = to_string(m);
    reverse(n.begin(), n.end());
    m = n.size() - 1;
}

void Solve()
{
    dp[0][0][0][0] = 1;
    for (int i = 0; i <= m; ++i)
    {
        for (int j = 1; j <= k; ++j)
            for (int t = 0; t < 2000; ++t)
                for (int h = 0; h < 10; ++h)
                    if (h * a[j] <= t)
                    {
                        dp[i][0][j][t] = (dp[i][0][j][t] + dp[i][0][j - 1][t - a[j] * h]) % mod;
                        dp[i][1][j][t] = (dp[i][1][j][t] + dp[i][1][j - 1][t - a[j] * h]) % mod;
                    }

        for (int j = 0; j < 2000; ++j)
            if (j % 10 < n[i] - '0')
            {
                dp[i + 1][0][0][j / 10] = (dp[i + 1][0][0][j / 10] + dp[i][0][k][j]) % mod;
                dp[i + 1][0][0][j / 10] = (dp[i + 1][0][0][j / 10] + dp[i][1][k][j]) % mod;
            }
            else if (j % 10 > n[i] - '0')
            {
                dp[i + 1][1][0][j / 10] = (dp[i + 1][1][0][j / 10] + dp[i][0][k][j]) % mod;
                dp[i + 1][1][0][j / 10] = (dp[i + 1][1][0][j / 10] + dp[i][1][k][j]) % mod;
            }
            else
            {
                dp[i + 1][0][0][j / 10] = (dp[i + 1][0][0][j / 10] + dp[i][0][k][j]) % mod;
                dp[i + 1][1][0][j / 10] = (dp[i + 1][1][0][j / 10] + dp[i][1][k][j]) % mod;
            }
    }
    cout << dp[m + 1][0][0][0] % mod;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    Read();
    Solve();
}