【题意】：

【题解】：设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