这题我和王队合力做，王队想到了第一个转化，我想到了第二个转化，但是并没有导出成型的做法，看来，关键时候的坚持确实十分重要。

不要被难度标签所吓到。现在来看，我每次都能隐约想到正解的一些东西，但难出做法，很可能是对算法理解不够深入。

但又该怎么提升呢？也许多做题是有用的。我也能感觉得出来，最近做的题质量有提升。希望这是好的开始。

首先，这题在圆上和在序列上做是没有区别的，两条在圆上相交的线段在序列上也是相交的，反之亦然。

那么，在序列上，线段相当于一段区间，而一堆有交的线段，看上去就像一个大区间。

事实上，对于一个连通块，我们考察其最左边的点 和最右边的点 ，一个连通块显然对应一个区间。

都观察到这里了，我居然想设计一个从前向后的 DP（

看来思考的时候，在草稿纸上写清楚已有的结论至关重要。

设 表示对应区间为 的连通块数，并附加限制：且 中没有点向 之外连边（包括我们所计数的连通块，也包括这个连通块以外，但在 中的点）。

设 表示 个点任意匹配的方案数，在 为偶数时，其为 ，在 为奇数时其为 。

设 表示区间 内还未确定匹配的点数（就是输入中未涉及到的点）。

首先，如果 ，那么 。

如果读者熟悉图计数的话，会知道一个计数连通块的套路：总方案减去 “ 号点所在连通块大小小于总数” 的方案。

这里也是要计数连通块，我们也还是先让 。

然后枚举 号点所在连通块不是 的方案数，即

综上所述，有转移式： 。

最后的答案就是 。

#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 5,P = 1e9 + 7;
int n,K;
int g[N],match[N];
int dp[N][N],sum[N];
inline int Cnt(int l,int r) { return sum[r] - sum[l - 1];}

int main()
{
	cin >> n >> K;n <<= 1;
	for(int i = 1;i <= K;i++)
	{
		int u,v;
		cin >> u >> v;
		match[u] = v;match[v] = u;
	}
	for(int i = 1;i <= n;i++)
		sum[i] = sum[i - 1] + (!match[i]);
	g[0] = 1;
	for(int i = 2;i <= n;i += 2)
		g[i] = 1ll * g[i - 2] * (i - 1) % P;
	int ans = 0;
	for(int len = 2;len <= n;len += 2)
		for(int i = 1;i + len - 1 <= n;i++)
		{
			int j = i + len - 1,flag = 1;
			for(int x = i;x <= j;x++)
				if(match[x] && (match[x] < i || match[x] > j)) { flag = 0;break;}
			if(!flag) continue; 
			dp[i][j] = g[Cnt(i,j)];
			for(int k = i;k < j;k++)
				dp[i][j] = (dp[i][j] + P - 1ll * dp[i][k] * g[Cnt(k + 1,j)] % P) % P;
			ans = (ans + 1ll * dp[i][j] * g[n - 2 * K - Cnt(i,j)] % P) % P;
		}
	cout << ans << endl;
	return 0;
}