ABC385 G
ddxrS
·
·
题解
题目翻译
对于一个 (1,2,\dots,N) 的排列 P=(P_1,P_2,\dots,P_N)，定义整数 L(P) 和 R(P)：
- 考虑 N 栋从左到右的建筑，其中第 i 栋建筑的高度为 P_i。然后 L(P) 表示从最左边能看到的建筑的数量，R(P) 表示从最右边能看到的建筑的数量。
更正式的说，L(P) 为满足对于所有 j<i 都有 P_j<P_i 的 i 的个数，R(P) 为满足对于所有 j>i 都有 P_i>P_j 的 i 的个数。
给定你整数 N 和 K。找出满足 L(P)-R(P)=K 的 (1,2,\dots,N) 的排列 P 的数量对 998244353 取模后的值。
思路
首先，高度为 N 的建筑会对 L(P) 和 R(P) 造成贡献。在 N 左边的建筑只可能会对 L(P) 造成贡献，在 N 右边的建筑只可能会对 R(P) 造成贡献。
接下来考虑 L(P)-R(P)=K 的限制，可以枚举 L(P)，那么 R(P) 也知道了。记对 L(P) 或 R(P) 造成贡献的建筑有 d 个，那么我们就需要求出剩下 N-d 栋建筑完全没造成贡献且只考虑这些建筑的方案数。
来考虑这样一种生成这 N 栋建筑的方案，将建筑按照高度从大到小插入，那么第 i 次插入（即高度为 N-i+1 的建筑）：
- 若 i=1，对 L(P) 和 R(P) 都造成贡献。
- 若 i=2，放在 N 的左边或右边，分别对 L(P) 或 R(P) 造成贡献。
- 若 i>2，放在最左边或最右边或者直接插到中间，分别对 L(P) 或 R(P) 造成贡献或者不造成贡献，其中插到中间的方案数为 i-2。
接下来我们就可以计算出方案了，定义 f_{i,j} 表示当前是第 i+2 次插入，其中 j 栋建筑没造成贡献且只考虑这些建筑的方案数，那么有：
f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times i
我们需要的就是 f_{n-2}。
那么对于 L(P)+R(P)-1=d 的方案数就是 C_{d-1}^{R(P)-1}\times f_{n-2,N-d}。
我们就可以在 O(N^2) 的复杂度内解决这个问题，时间瓶颈在求解 f 上。
但是，你可以发现，要求的就是第一类斯特林数行，直接套上来就行了。
时间复杂度 O(N\log N)。