题解

蒟蒻只会\(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 <bits/stdc++.h>

#define MAXN 50005

//#define ivorysi

#define enter putchar('\n')

#define space putchar(' ')

#define fi first

#define se second

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

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<class T>

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;

}