「FJOI2016」建筑师 题解

题意

$n$ 个建筑，高度是 $1$ 到 $n$ 的一个排列

从左看能看到 $A$ 个，从右看能看到 $B$ 个

求排列方案数 $\bmod 10^9+7$

核心公式 答案 = $C(A+B-2, A-1) × S(n-1, A+B-2)$

其中：

$C(n,k)$：组合数

$S(n,k)$：第一类斯特林数（$n$ 个元素分 $k$ 个圆排列）

为什么？ 最高建筑（高度 $n$）一定被看到

剩下 $n-1$ 个建筑分成 $A+B-2$ 个"组"（每组以可见建筑开头）

从这些组中选 $A-1$ 个放左边，$B-1$ 个放右边

算法

预处理 斯特林数 $S(n,k)$

递推：$S(n,k) = S(n-1,k-1) + (n-1)×S(n-1,k)$

$n≤50000$，$k≤200$（因为 $A,B≤100$）

组合数 $C(n,k)$

直接计算或预处理

查询 $O(1)$ 计算：$C(A+B-2, A-1) × S(n-1, A+B-2) \bmod M$

复杂度 预处理：$O(n×200)$ 可接受

查询：$O(1)$，$T≤200000$ 可过