第一类斯特林数
[斯特林轮换式 S[n][k]表示将n个两两不同的元素,划分为k个非空圆排列的方案数
]
递推式:
[S[n][k] = S[n-1][k-1]+(n - 1)cdot S[n-1][k]
]
边界:
[S[n][0]=[n=0]
]
HDU 4372
题意:
有n座高分别为(1sim n)的城市在一条水平线上,从左能看到(F)座城市,从右能看到B座城市,问有几种城市的排列方案。
题解:
首先最高的那座楼无论从左还是从右都会看到,因此最高的那座位置都是固定的。
从左看的(F - 1)座必然是高度递增的,因此我们可以把这(F-1)座楼分组,每组的最左端也就是每组的最高的那座楼。组内剩下的$ k - 1$ 座进行全排列有((k - 1)!) 种情况,相当于(k)个元素进行圆排列。对于每一组进行圆排列,又由于前(F-1)是升序,因此相当于再从(F-1+B-1)中选择(F-1)个。
因此
[ans = binom{F-1+B-1}{F-1} cdot S[n-1][F-1+B-1]
]
ll C[2005][2005];
ll S[2005][2005];
void get_C()
{
C[0][0] = 1;
for (int i = 1; i <= 2000; i++)
{
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = C[i - 1][j] + C[i - 1][j - 1], C[i][j] %= MOD;
}
}
void get_S() {
S[0][0] = 1;
for (int i = 1; i <= 2000; i++) {
for (int j = 1; j <= i; j++)
S[i][j] = S[i - 1][j - 1] + (i - 1) * S[i - 1][j] % MOD, S[i][j] %= MOD;
}
}
int main() {
get_C();
get_S();
int T = readint();
while (T--) {
ll n = readll();
ll f = readll();
ll b = readll();
if (f - 1 + b - 1 > n) {
puts("0");
continue;
}
ll res = C[f - 1 + b - 1][f - 1] * S[n - 1][f - 1 + b - 1];
res %= MOD;
Put(res);
puts("");
}
}