自动搬运

查看原文

来自洛谷，原作者为

	鏡音リン 希望大家都能成为自己想要的样子呐

搬运于2025-08-24 22:23:29，当前版本为作者最后更新于2020-07-18 10:59:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目链接

subtask 0

首先破环成链，把点依次从 $1$ 到 $n$ 编号，并用 $(x,y)$ 表示从点 $x$ 到点 $y$ 的一条线段，其中 $x<y$。

则两条线段 $(x_1,y_1),(x_2,y_2)$ 相交当且仅当 $x_1<x_2<y_1<y_2$ 或 $x_2<x_1<y_2<y_1$。

搜索枚举所有线段方案并判断即可。

subtask 1

用 $f(n,m)$ 表示答案。若点 $1$ 没有连接线段，方案数为 $f(n-1,m)$。若点 $1$ 上有线段，考虑所有从点 $1$ 连接的线段 $(1,x)$ 中 $x$ 的最大值，枚举这个最大值为 $i$。则链被点 $i$ 分成两部分，左半部分有 $i$ 个点，右半部分有 $n-i+1$ 个点（两部分都包括点 $i$）。这两部分点之间不可能有线段相连，可以相互独立计算。枚举左半部分中的线段数 $j$，可以得到递推式：

$$f(n,m)=f(n-1,m)+\sum_{i=2}^{n}\sum_{j=0}^{m-1}f(i,j)f(n+1-i,m-1-j) $$

按照此式递推，时间复杂度 $O(n^2m^2)$。

subtask 2

可以看出上述递推式其实为卡特兰三角形（OEIS A001263）的变形，且有 $f(n,m)=T(n+m-1,n-1)$。代入通项公式得

$$f(n,m)=\frac{(n+m-2)!(n+m-1)!}{(n-2)!(n-1)!m!(m+1)!} $$

subtask 3

同样爆搜判断即可。

subtask 4,5

设 $f(x,l,r,y)$ 表示数组 $\{x,a[l],a[l+1],\dots,a[r],y\}$ 上的答案。

若 $x=0$ 则 $f(x,l,r,y)=f(a[l],l+1,r,y)$，同理若 $y=0$ 则 $f(x,l,r,y)=f(x,l,r-1,a[r])$。

否则，同样考虑枚举第一个点（即点 $l-1$ ）上连接的线段中，连接到的最大编号为 $i$ 。若 $i=r+1$ 则贡献为 $f(x-1,l,r,y-1)$，否则点 $i$ 把链分成两个部分，可以独立计算。枚举点 $i$ 向左半部分连接的线段数 $j$，有以下递推式：

$$f(x,l,r,y)=f(x-1,l,r,y-1)+\sum_{i=l}^r\sum_{j=0}^{a[i]-1}f(x-1,l,i-1,j)f(a[i]-1-j,i+1,r,y) $$

可以 dp，也可以实现为记忆化搜索（不确定能卡过 subtask5），优秀的实现可以达到 $O(m^3)$ 的时间复杂度。

也可以考虑把每一个点 $i$ 拆成 $a[i]$ 个点，每个点只能连接一条线段，且原本属于同一个点的点不能连接线段。按照上面的思路进行区间dp，代码会好看一点（常数小一点）。

subtask6

设 $dp(i-1,j)$ 为前 $i-1$ 个点连接了 $j$ 条线段的方案数。设前 $i-1$ 个点的度数和为 $S$ ，那么剩余的没有连接的度数为 $S-2j$。对于新增的一个度数为 $a_i$ 的点，考虑该点有 $t$ 条线段连向前面的点，有转移

$$dp(i-1,j)\rightarrow dp(i,j+t),t\le a_i,t\le S-2j$$

直接枚举 $t$ 转移时间复杂度为 $O(m^2)$。使用前缀和可以优化成 $O(nm)$，但本题中没必要。