题解 [AGC028D] Chords

首先， 按照boshi巨佬的说法， 考虑每种联通块的出现次数。如果可以求出， 答案就是每种联通块的出现次数和。

再按照boshi巨佬的说法， 一种定义联通块长相的方法是用编号最小的点和编号最大的点表示。

于是设(f[l][r])为(l, r)连通且外面的点不连接到里面的点， 里面的所有边都任意连接的方案数。

由于(l, r)连通不是很好做， 所以就用任意连的方案数目减去连通的方案数目。

设(g[l][r])为([l, r])内的点任意连接的方案数目， 有：

(f[l][r] = g[F(l, r)] - sum f[l][k] imes g[F(k + 1, r)])

(F(l, r)) 指([l, r])之间没有被强制选的点数。

那么显然这个方程就是在枚举本区间靠左的连通块的大小。

容易发现的事实是， 合法的(f[l][r])区间的长度一定是个偶数。 然后(dp)前注意处理一下这个区间是否有连接到外面去的点就好了。

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

#define R register
const int N = 600 + 5;
const int P = 1e9 + 7;

inline int read() {
	int x = 0, f = 1; char a = getchar();
	for(; a > '9' || a < '0'; a = getchar()) if(a == '-') f = -1;
	for(; a >= '0' && a <= '9'; a = getchar()) x = x * 10 + a - '0';
	return x * f;
}

int n, m;
int g[N], fb[N], to[N];
int f[N][N];

inline int F(int l, int r) {
	return r - l + 1 + fb[l - 1] - fb[r];
}

int main() {
	#ifdef IN
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	#endif
	n = read(); m = read(); n <<= 1;
	for(R int i = 1; i <= m; i ++) {
		int x = read(), y = read();
		fb[x] = fb[y] = 1;
		to[x] = y; to[y] = x;
	}
	for(R int i = 1; i <= n; i ++) fb[i] += fb[i - 1];
	g[0] = 1;
	for(R int i = 2; i <= n; i += 2) g[i] = 1LL * g[i - 2] * (i - 1) % P;
	int ans = 0;
	for(R int i = 1; i <= n; i ++) 
		for(R int j = i; j <= n; j ++)
			if((j - i) & 1) {
				bool flg = 0;
				for(R int k = i; k <= j; k ++)
					if(to[k] && (to[k] < i || to[k] > j)) flg = 1;
				if(flg) continue;
				f[i][j] = g[F(i, j)];
				for(R int k = i + 1; k < j; k ++)
					f[i][j] = (f[i][j] - 1LL * f[i][k] * g[F(k + 1, j)] % P + P) % P;
				ans = (ans + 1LL * f[i][j] * g[F(1, i - 1) + F(j + 1, n)] % P) % P;
			}
	printf("%d
", ans);
	return 0;
}