[NOI Online #2 入门组]建设城市

记 $h_i$ 表示第 $i$ 个楼的高度。题意就是说求满足下面三个条件的数列的个数：

1. $h_1 \le h_2 \le \cdots \le h_n, h_{n+1} \ge h_{n+2} \ge \cdots \ge h_{2n}$
2. $h_x = h_y$
3. $\forall 1 \le i \le 2n, h_i \in [1, m]$

如果没有 $h_x = h_y$ 的限制，方案数应该是什么呢？

显然上升部分和下降部分的方案数是相等的，我们只考虑前面一个部分（也就是用 $[1, m]$ 拼长度为 $n$ 的不下降序列的方案数 $f(n, m)$）。利用隔板法的思想，可以先把楼排成一行，在中间依次插上 $m - 1$ 个隔板，相邻两个隔板之间的楼的高度相等，求不同的插法。

当然，这时可能会有多个隔板在一个位置，比如楼房高度为 $\{1, 1, 3\}$ 时，隔板的插法就是 $\{ \circ \circ \ |\ |\ \circ \}$。

这违背了隔板法的要求，所以我们加 $m$ 个楼进去，确保这些新加的楼的高度分别为 $1 \sim m$，然后就可以用隔板法了。

比如 $m = 3$，$\{ \circ\circ |\circ |\circ\circ \}$ 这种插法对应的就是 $\{1, 3\}$，因为我们要在每两个隔板见去掉一个。

所以，相当于是有 $n + m$ 个楼，插 $m - 1$ 个隔板的方案数。隔板显然是插在间隔里，$n + m$ 个楼有 $n+m-1$ 个间隔，所以，方案数就是：

$$ f(n, m)=\binom{n+m-1}{m-1} $$

接下来，考虑加上 $h_x = h_y$ 的条件。

• 如果 $x, y$ 在同一侧，那么显然 $h_x , h_{x+1} \cdots h_y$ 都是相等的，可以视作一个楼（所以少了 $y - x$ 个楼），所以，这一侧的方案数就是 $f(n - (y - x), m) = f(n + x - y, m)$，另一侧不变，也就是 $f(n, m)$。综上，答案为：

$$ f(n+x-y, m) \times f(n, m) $$

• 如果 $x, y$ 不在同一侧，不妨枚举一下 $h_x$ 等于多少，比如枚举到的是 $h_x = i$，那么序列会分为 $4$ 段：

1. $h_1 \sim h_{x - 1}$ 这 $x - 1$ 个楼应当 $\in [1, i]$，所以方案数为 $f(x - 1, i)$；
2. $h_{x+1} \sim h_n$ 这 $n - x$ 个楼应当 $\in[i, m]$，所以方案数为 $f(n - x, m - i + 1)$；
3. $h_{n+1} \sim h_{y-1}$ 这 $y-n-1$ 个楼应当 $\in[i, m]$，所以方案数为 $f(y-n-1, m - i + 1)$；
4. $h_{y+1} \sim h_{2n}$ 这 $2n - y$ 个楼应当 $\in[1, i]$，所以方案数为 $f(2n - y, i)$。

然后，对于每个 $i$ 的加起来就是了，也就是说，答案为：

$$ \sum_{i=1}^{m} f(x - 1, i) \times f(n - x, m - i + 1) \times f(y-n-1, m - i + 1) \times f(2n - y, i) $$

提前 $O(n)$ 预处理阶乘和逆元，这题就解决了，情况 1 计算时间复杂度 $O(1)$，情况 2 是 $O(m)$，可以通过此题，代码就不贴了。

其实把 n 开到 1e9 也没啥呀，分块打表很香啊

[NOI Online #2 入门组]建设城市

原文：https://www.cnblogs.com/syksykCCC/p/NOIO2-J3.html