【題意】：

【題解】：設dp[i][j][k]表示當前長度為i，最大值為j，已經更新了k次的合理方案數。
               轉移方程 dp[i][j][k] = dp[i-1][j][k] * j + ∑dp[i-1][1...j-1][k]
               由于狀態數高達100 * 300 * 100，用上面的轉移方程顯然會TLE。觀測轉移方程，我們很容易想到用部分和優化，這樣就可以把轉移降為O(1)。
               最后 ans = ∑dp[n][i...m][p].

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define ll long long
 6 const ll MOD = 1000000007LL;
 7 ll dp[110][310][110];
 8 int n, m, p;
 9 void solve() {
10     for(int i = 0; i <= n; i++) 
11         for(int j = 0; j <= m; j++)
12             for(int k = 0; k <= p; k++)
13                 dp[i][j][k] = 0;
14     for(int i = 1; i <= m; i++) dp[1][i][0] = 1;
15     for(int i = 2; i <= n; i++) {
16         for(int k = 0; k <= p && k < i; k++) {
17             ll sum = 0;
18             for(int j = 1; j <= m; j++) {
19                 dp[i][j][k] += dp[i-1][j][k] * j;
20                 if(k) dp[i][j][k] += sum;
21                 while(dp[i][j][k] >= MOD) dp[i][j][k] -= MOD;
22                 sum += dp[i-1][j][k-1];
23             }
24         }
25     }
26     ll ans = 0;
27     for(int i = 1; i <= m; i++) ans += dp[n][i][p];
28     printf("%lld\n", ans % MOD);
29 }
30 
31 int main() {
32     int T;
33     scanf("%d", &T);
34     while(T--) {
35         scanf("%d%d%d", &n, &m, &p);
36         solve();
37     }
38     return 0;
39 }
40