[FJOI2016] 建筑师

发表于 | 阅读次数：

$40$分

乱搞，$DP$

$100$分

法$1$

我们可以用$40$分的做法打一张表，然后找找规律就发现$ans=C^{A+1}{A+B-2} *S^{A+B-2}{n-1}$了。

啥？你说你不会$Stirling$数？

出门左转具体数学，包教包会

法$2$

我们理性分析一下

我们可以先挑出最高的位置，直接丢到一边去。

于是就变成变为在一个$n$层的分层图上，每次往下走一层，选择$A+1$或$B+1$或不变。

有$3$种边

第$1$,$2$种边都是$1$条，第$3$种边由$n - 2$条递减到$0$条。

设$f_{i,j}$为从后往前推到第$i$层，选了$j$条改变$A$,$B$的边，选边的方案数。

于是我们就有以下递推式

$f_{i,j}=(i-1)*f_{i-1,j}+f_{i-1,j-1}$

于是
$ans=C^{A+1}{A+B-2}*f{n-1,A+B-2}$

然后你就会发现$f$的递推式和$Stirling$数一模一样….

我们预处理一下组合数$C$和$f$就可以通过此题了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <stdio.h>
#define reg register
#define MAXN 50010
#define mod_v 1000000007

using namespace std;

int T, n, A, B, C[210][110], S[MAXN][210];

int main() {
	C[0][0] = 1;
	for(reg int i = 1; i <= 200; ++i) {
		C[i][0] = 1;
		for(reg int j = 1; j <= i && j <= 100; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod_v;
	}
	S[0][0] = 1;
	for(reg int i = 1; i <= MAXN - 10; ++i) { for(reg int j = 1; j < i && j <= 200; ++j) S[i][j] = (S[i - 1][j - 1] + 1ll * (i - 1) * S[i - 1][j]) % mod_v; if(i <= 200) S[i][i] = 1; }
	cin >> T;
	while(T--) {
		cin >> n >> A >> B;
		cout << (1ll * C[A + B - 2][A - 1] * S[n - 1][A + B - 2] % mod_v) << endl;
	}
	return 0;
}