$ \text{[AGC028D] Chords 题解}$
整体来讲比较中规中矩的一个题。
首先这个圆上给到你你就没法处理。常规的操作是断环成链，发现实际上圆上线段相交等价于线段上线段“真相交”，即不包含的相交。然后你还是不会做。看题目让求什么，求所有方案中联通块的个数和你显然是不会的，不放考虑枚举每个联通块算全局中它的贡献。
想到这里这题你基本上其实就做完了。常规地设 \(f(l,r)\) 表示 \((l,r)\) 区间内是一个联通块的方案数，那么常规的容斥一下，枚举第一个“小联通块”的位置，转移式子是一个类似于 \(f(l,r)=g(\dfrac{r-l+1}2)-f(l,k)\times g(\dfrac{r-k}2)\) 的东西，\(g\) 表示的是乱排的方案数，容易发现 \(g(i)=\prod_{1}^{2i}i[2|i]\)。注意减去已经有的线段端点个数即可。判一下区间无解的情况，答案是一个 \(\sum f(l,r)g(x)\) 的形式，\(x\) 就是左右两边的自由点个数。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 605, mod = 1e9 + 7;
int n, k;
int f[N][N], g[N];
int ml[N], mr[N], vis[N], num[N][N];signed main() {ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;for (int i = 1; i <= k; i++) {cin >> ml[i] >> mr[i];if (ml[i] > mr[i]) swap(ml[i], mr[i]);vis[ml[i]] = vis[mr[i]] = 1;}for (int i = 1; i <= 2 * n; i++)for (int j = i; j <= 2 * n; j++)for (int t = i; t <= j; t++)num[i][j] += vis[t];g[0] = 1;for (int i = 1; i <= n; i++) g[i] = g[i - 1] * (2 * i - 1) % mod;for (int len = 2; len <= 2 * n; len += 2)for (int l = 1; l + len - 1 <= 2 * n; l++) {int r = l + len - 1, fg = 0;for (int i = 1; i <= k; i++)if ((ml[i] < l && mr[i] >= l && mr[i] <= r) || (mr[i] > r && ml[i] >= l && ml[i] <= r)) fg = 1;if (fg) continue;f[l][r] = g[(r - l + 1 - num[l][r]) / 2];for (int t = l + 1; t + 1 < r; t++) {f[l][r] -= f[l][t] * g[(r - t - num[t + 1][r]) / 2] % mod;f[l][r] = (f[l][r] % mod + mod) % mod;}}int ans = 0;for (int l = 1; l <= 2 * n; l++)for (int r = l + 1; r <= 2 * n; r += 2)ans = (ans + f[l][r] * g[max(0ll, (l - 1 + 2 * n - r - num[1][l - 1] - num[r + 1][2 * n]) / 2)] % mod) % mod;cout << ans << '\n';return 0;
}