• 狀態表示：定義狀態 \(dp[i][j][k]\) ，用于表示考慮前 \(i\) 個物品，背包容量恰好為 \(j\) ，且花費恰好為 \(k\) 的方案數，屬性為“Sum”。由于空背包也算作一種方案，故 \(dp[0][0][0]=1\)。
• 狀態計算：對于\(dp[i][j][k]\)：
  • 不可選第 \(i\) 種物品：若背包容積不夠( \(j\le 0\) )或物品價格大于當前花費( \(g[i]>k\) )時，第 \(i\) 種物品不可選，此時直接轉移自第 \(i-1\) 個物品的狀態；
  • 可選第 \(i\) 種物品：若 \(j>0\) 且 \(k\ge g_i\) ，則可選第 \(i\) 種物品，此時又分 \(2\) 種情形：
    • 選第 \(i\) 種物品：花費 \(1\) 個體積購買物品 \(i\)，由于為完全背包問題，同一物品可購買多次，狀態轉移自第 \(i\) 種物品。
    • 不選第 \(i\) 種物品：若已達到約束要求，則第 \(i\) 種物品沒必要選，則直接轉移自第 \(i-1\) 個物品的狀態
• 因此對于 \(dp[i][j][k]\) ，其滿足要求的狀態有選 \(i\) 和沒必要選 \(i\) 兩種，累加這兩種情況。最后遍歷所有 \(\le V\)的情形累加即可。

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

void solve() {
    int n, m, V;
    cin >> n >> m >> V;
    vector<int> g(n+1);
    for (int i = 1; i <= n; i++) cin >> g[i];
    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(m+1, vector<int>(V+1, 0)));
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= V; k++) {
                dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k]) % MOD;//注意求方案數問題是累加
                if (j > 0 && k >= g[i]) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i][j-1][k-g[i]]) % MOD;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= V; i++) {
        ans = (ans + dp[n][m][i]) % MOD;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}