题解

蒟蒻只会\(O(nAB)\)的dp= =

那么先说答案

\(S_{u}(n - 1,a + b - 2) * \binom{a + b - 2}{a - 1}\)

其中\(S_{u}(n,m)\)表示无符号第一类斯特林数（求n个数排列成m个圆的方案数）

怎么样呢，除了最高的柱子，剩下的一定是 一个高的柱子，后面跟着一些小于它的柱子，这就像一个圆排列，我们从最大的值那里把这个圆断开，我们要求的就是把n - 1个数分成a +b -2个圆排列

然后排到前面a - 1个，用组合数算一下

代码

#include 
    
     #define MAXN 50005//#define ivorysi#define enter putchar('\n')#define space putchar(' ')#define fi first#define se secondusing namespace std;typedef long long int64;typedef double db;template
     
      void read(T &res) {    res = 0;char c = getchar();T f = 1;    while(c < '0' || c > '9') {    if(c == '-') f = -1;    c = getchar();    }    while(c >= '0' && c <= '9') {    res = res * 10 + c - '0';    c = getchar();    }    res *= f;}template
      
       void out(T x) {    if(x < 0) {putchar('-');x = -x;}    if(x >= 10) {    out(x / 10);    }    putchar('0' + x % 10);}const int MOD = 1000000007;int64 S[MAXN][205],fac[205],invfac[205],inv[205];int T,N,A,B;int64 C(int n,int m) {    if(n < m) return 0;    return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;}void Solve() {    S[0][0] = 1;    for(int i = 1 ; i <= 50000 ; ++i) {    for(int j = 1 ; j <= 200 ; ++j) {        S[i][j] = (S[i - 1][j] * (i - 1) + S[i - 1][j - 1]) % MOD;    }    }    fac[0] = 1;    for(int i = 1 ; i <= 200 ; ++i) fac[i] = fac[i - 1] * i % MOD;    inv[1] = 1;    for(int i = 2 ; i <= 200 ; ++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;    invfac[0] = 1;    for(int i = 1 ; i <= 200 ; ++i) invfac[i] = invfac[i - 1] * inv[i] % MOD;    read(T);    while(T--) {    read(N);read(A);read(B);    out(S[N - 1][A + B - 2] * C(A + B - 2,A - 1) % MOD);enter;    }}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}