Bài toán: để kiểm tra một dãy số không giảm ~S_1, S_2, \cdots, S_N~ có thỏa mãn yêu cầu đề bài hay không, cần kiểm tra mọi dãy con độ dài ~k~ có tổng nhỏ nhất lớn hơn mọi dãy con độ dài ~k - 1~ có tổng lớn nhất hay không.

Subtask ~1~: ~t = 1, N \le 15~

Xét các dãy không giảm ~S_1, S_2, \cdots, S_N~, với mỗi dãy, kiểm tra dãy hợp lệ hay không, số lượng dãy không giảm độ dài ~N~ cần xét là ~C_{2N - 1}^{N}~. Duyệt quay lui với độ phức tạp: ~\mathcal{O}(N \times C_{2N - 1}^{N})~.

Subtask ~2~: ~t = 1, 15 < N \le 35~

Thay vì tạo ra một dãy không giảm hoàn chỉnh rồi mới kiểm tra tính hợp lệ, ta xây dựng dần dãy từ hai đầu như sau: đầu tiên gán giá trị ~S_1 = 1..N~, sau đó duyệt hai vòng để chọn giá trị cho ~S_2~ và ~S_N~ trong đoạn giá trị ~1..N~, với điều kiện là ~S_1 \le S_2 \le S_N~ và ~S_1 + S_2 > S_N~. Tiếp tục chọn giá trị cho ~S_3~ và ~S_{N - 1}~ với điều kiện:

~S_2 \le S_3 \le S_{N - 1} \le S_N~ và ~S_1 + S_2 + S_3 > S_{N - 1} + S_N~. Cứ tiếp tục như vậy cho đến khi chỉ còn lại ~0~ hoặc ~1~ số. Nếu không còn phần tử nào để chọn giá trị, ta đã xây dựng được một dãy không giảm thỏa mãn. Thuật toán đệ quy quay lui bằng duyệt nhánh cận giải quyết bài toán ~N \le 35~ với độ phức tạp: ~\mathcal{O}(N \times C_{2N - 1}^{N})~.

Subtask ~3~: ~35 < N \le 100~

Ta thấy ~S_k~ thành tổng của các giá trị ~x_i~, cụ thể ta đặt ~S_k = 1 + x_1 + x_2 + \cdots + x_k~ (với ~x_i \ge 0~ cho bất kỳ ~i~ nào). Dễ thấy ta luôn có thể tìm được một dãy ~x~ thỏa mãn. Thay thế điều này vào điều kiện cho ~\left \lfloor{\frac{N}{2}}\right \rfloor~ khi đó:

- Đếm số bộ số nguyên không âm (~x_1, x_2, \cdots, x_N~) thoả mãn các điều kiện sau:

• Vì ~S_k \le N~ và ~S_i \le S_{i + 1}~ với ~1 \le i < N~ nên:

  ~x_1 + x_2 + \cdots + x_N \le N - 1~

• ~\sum_{i=1}^{k+1} S_i > \sum_{i=N-k+1}^{N} S_i~

  ~\Leftrightarrow (k+1) + \sum_{i=1}^{k+1} (k+2-i)x_i > k + \sum_{i=1}^{N-k} kx_i + \sum_{i=N-k+1}^{N} (N+1-i)x_i~

  ~\Leftrightarrow \sum_{i=1}^{k+1} (k+2-i)x_i \ge \sum_{i=1}^{N-k} kx_i + \sum_{i=N-k+1}^{N} (N+1-i)x_i~

• Từ đó ta có:

  ~x_1 \ge [x_2, x_3, ..., x_N] \times [0,1,2,3,...,3,2,1]~

  (trong đó dấu "~\cdot~" biểu diễn tích đề các)

- Giả sử ~x_2, x_3, ..., x_N~ được cố định:

• ~x_2 + x_3 + \dots + x_N = a~

• ~[x_2, x_3, ..., x_N] \times [0,1,2,3,...,3,2,1] = b~

- Từ ràng buộc đầu tiên, ~x_1 \leq N - 1 - a~, và từ ràng buộc thứ hai, ~x_1 \ge b~. Do đó, số lượng giá trị có thể có của ~x_1~ chính xác là ~\max(N-a-b,0)~.

Công thức quy hoạch động:

- Đặt ~[c_2, c_3, c_4, c_5, ..., c_{N-2}, c_{N-1}, c_N] = [0,1,2,3,...,3,2,1]~.

- Gọi ~dp_{i,j,k}~ là số lượng cách xây dựng dãy ~x_i, x_{i+1}, ..., x_N~ sao cho:

• ~x_i + x_{i+1} + \dots + x_N = j~

• ~[x_i, x_{i+1}, ..., x_N] \times [c_i, c_{i+1}, ..., c_N] = k~.

Rút ra được công thức: ~dp_{i,j,k} = \sum_{t=0}^{\min(j,\left \lfloor{k/c_i}\right \rfloor)} dp_{i+1,j-t,k-c_it}.~

Ta chỉ cần tính tổng ~\max(N-a-b,0)~ là sẽ ra được kết quả với phức tạp: ~\mathcal{O}(N^3 \log N)~.

Subtask 4: ~100 < N \le 1000~

Ta luôn có ~x_2, x_3, \dots, x_N~ được cố định:

• ~x_2 + x_3 + \dots + x_N = a~

• ~[x_2, x_3, \dots, x_N] \times [0,1,2,3,\dots,3,2,1] = b~

Nhận xét giá trị duy nhất là ~a + b = [x_2, x_3, \dots, x_N] \times [1,2,3,4, \dots, 4,3,2]~:

• Tìm tổng của ~\max(N - [x_2, x_3, \dots, x_N] \times [1,2,3,4, \dots, 4,3,2], 0)~ cho tất cả các bộ số nguyên không âm ~(x_2, x_3, \dots, x_N)~.

• Đặt ~[c_2, c_3, c_4, c_5, \dots, c_{N-2}, c_{N-1}, c_N] = [1,2,3,4, \dots, 4,3,2]~.

• Gọi ~dp_{i,j}~ là số lượng cách xây dựng dãy ~x_i, x_{i+1}, \dots, x_N~ sao cho: ~[x_i, x_{i+1}, \dots, x_N] \times [c_i, c_{i+1}, \dots, c_N] = j~

• Khi đó: ~dp_{i,j} = \sum_{k=0}^{\lfloor j / c_i \rfloor} dp_{i+1, j - k c_i}~

Từ đây ta đã hết tất cả số lượng các trường hợp giá trị ~a + b~ khi đã cố định ~x_2, x_3, \dots, x_N~. Tính tổng ~\max(N - (a + b), 0)~ là sẽ ra được kết quả với độ phức tạp: ~\mathcal{O}(N^2 \log N)~.

Subtask 5: Công thức ở subtask ~4~ có thể được tính trước bằng mảng tiền tố theo một khoảng cách ~c_i~, mỗi lần tính xong giá trị ở ~i~, ta chạy ~j~ để tính tổng tiền tố theo khoảng cách ~c_{i-1}~ cho lần tính tiếp theo. Độ phức tạp: ~\mathcal{O}(N^2)~.

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

int dp[2][5005];
int pre[2][5005];
int c[5002];
int MAXK[5002];

int main() {
    if(fopen("SCORES.inp","r"))
    {
        freopen("SCORES.inp","r",stdin);
        freopen("SCORES.out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;

        for (int i = 2; i <= N; i++){
            c[i] = min(i - 1, N - i + 2);

        }


        memset(dp, 0, sizeof(dp));
        memset(pre,0, sizeof(pre));
        dp[(N + 1)&1][0] = 1;
        for(int j = 0;j <= N;j++)
            if(j >= c[N])
                pre[N&1][j] = pre[N&1][j - c[N]] + dp[(N+1)&1][j];
            else
                pre[N&1][j] = dp[(N+1)&1][j];

        for (int i = N; i >= 2; i--) {
            for (int j = 0; j <= N; j++) {
                dp[i&1][j] = pre[i&1][j];

                if(i != 2) {
                    if(j >= c[i-1])
                        pre[(i-1)&1][j] = pre[(i-1)&1][j - c[i - 1]] + dp[i&1][j];
                    else
                        pre[(i-1)&1][j] = dp[i&1][j];
                    if(pre[(i-1)&1][j] >= MOD)
                         pre[(i-1)&1][j] -= MOD;
                }
            }
        }


        long long res = 0;
        long long x;
        for (int b = 0; b <= N; b++) {
            x = dp[2&1][b];
            res = (res + x*max(0ll, 1ll*(N - b))%MOD);
            if(res >= MOD)
                res -= MOD;
        }


        cout << res << "\n";
    }
    return 0;
}