# Mở bài
sau khi kết thúc contest prehsg11, mình có vào xem thử code bài 3 thì thấy các bạn chỉ đặt cận để giải trong khi sol chuẩn của mình thì không phải thế : ), nên mình viết blog để hướng dẫn cách tiếp cận công thức QHĐ cho bài 3.

# Vấn đề
Cho $2$ số $n$ và $m$, tính số lượng mảng $a$ gồm $n$ phần tử sao cho $0 \le a_1 \le a_2 \le .... \le a_n$ và $a_1 + a_2 + .... + a_n = m$.

link nộp bài: https://lqdoj.edu.vn/problem/thabai3
# Giới hạn
$1 \le n, m \le 2000$

# Ý tưởng
Giả sử ta có $1$ mảng $a$ gồm $n$ phần tử, ta gọi $d$ là mảng hiệu của mảng $a$ khi
$d_i = a_i - a_{i - 1}$ (với mọi $i$ từ $2$ đến $n$) và $d_1 = a_1$. Sau khi có khái niệm về mảng hiệu, ta có thể thấy 3 điều:
- Thứ nhất là $a_1 + a_2 + ... + a_n = d_1 * n + d_2 * (n - 1) + ... + d_n * 1$
(Phần này mình sẽ để các bạn tự chứng minh :)) ).
- Thứ hai là $2$ mảng sẽ được xem là khác nhau nếu mảng hiệu của nó khác nhau.
- Thứ ba là nếu $1$ mảng không âm không giảm thì phải có các phần tử trong mảng hiệu là không âm.

Quay lại với bài toán mở đầu, ta có thể xây dựng quy hoạch động dựa trên mảng hiệu thay vì phải xây dựng trên mảng $a$. Cụ thể, ta tính số lượng mảng hiệu $d$ không âm gồm $n$ phần tử thỏa mãn $d_1 * n + d_2 * (n - 1) +...+ d_n * 1 = m$. Vì các phần tử của mảng $d$ không phụ thuộc vào nhau nên ta có thể viết lại công thức thành $d_1 * 1 + d_2 * 2 +...+ d_n * n = m$. Từ công thức trên thì có thể dùng QHĐ 2 chiều để giải trong độ phức tạp là $O(n * m * log(m))$

# code

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

int mod = 1e9 + 7;
const int N = 2e3 + 10;

int f[N][N];

void add(int &a, int b) {
    a += b;
    while (a >= mod)
        a -= mod;
}

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

    int n, m;
    cin >> n >> m;

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k * i <= j; k++) {
                add(f[i][j], f[i - 1][j - k * i]);
            }
        }
    }

    cout << f[n][m] << '\n';
}

# Kết bài
Chúc mọi người smurf giải tỉnh :--)))

# Bonus
Bạn hãy thử nghĩ cách giải bài này trong $O(n * m)$.