题解 环

· · 题解

题目链接

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)，但本题中没必要。