题解 AT4438 【[AGC028D] Chords】

· · 题解

令 n = 2N。

把圆上看成序列上也可以，也就是说如果 [l_1, r_1] 和 [l_2, r_2] 相交但不包含，那么转化到圆上他们就是相交的。

考虑对于每个连通块，计算它对答案的贡献次数，加起来就是答案。

我们发现一个连通块在序列上一定对应了一个区间，满足连通块完全在这个区间内，而且区间端点属于连通块。

但是要注意并不是这个区间内全都是这个连通块，可能其中还有小连通块。

则令 dp(i, j) 表示区间 [i, j] 内任意连边，且 i, j 在同一连通块内的区间内连边方案数。

枚举这个区间 [i, j]，它的长度一定为偶数。则可以发现这个区间内的点不能向区间外连边，这是有利于统计的。

如果区间内任意连边，那么方案数就是 dp(i, j) = g(c(i, j))。
其中 g(x) 表示 x 个点的环任意连边的方案数，当 x 为偶数时等于 1 \cdot 3 \cdot 5 \cdot \cdots \cdot (x - 1)，否则为 0。
而 c(i, j) 为 [i, j] 内还没确定连边情况的点的个数。

但是还有第二个条件，就是 i, j 在同一个连通块内。考虑容斥，如果不在，枚举 i 连通块的区间右端点 k。

有 \displaystyle dp(i, j) = g(c(i, j)) - \sum_{k = i}^{j - 1} dp(i, k) \cdot g(c(k + 1, j))。

最后求出所有 dp(i, j) 后，就有答案等于 \displaystyle \sum dp(i, j) \cdot g(n - 2K - c(i, j))。

时间复杂度为 \mathcal O (n^3)，评测链接。