记 $h_i$ 表示第 $i$ 个楼的高度. 题意就是说求满足下面三个条件的数列的个数:
- $h_1 \le h_2 \le \cdots \le h_n, h_{
- n+1
- } \ge h_{
- n+2
- } \ge \cdots \ge h_{
- 2n
- }$
- $h_x = h_y$
- $\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$ 段:
$h_1 \sim h_{x - 1}$ 这 $x - 1$ 个楼应当 $\in [1, i]$, 所以方案数为 $f(x - 1, i)$;
$h_{x+1} \sim h_n$ 这 $n - x$ 个楼应当 $\in[i, m]$, 所以方案数为 $f(n - x, m - i + 1)$;
$h_{n+1} \sim h_{y-1}$ 这 $y-n-1$ 个楼应当 $\in[i, m]$, 所以方案数为 $f(y-n-1, m - i + 1)$;
$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 入门组] 建设城市
来源: http://www.bubuko.com/infodetail-3523734.html