Submission #3589359

---

Source Code Expand

#include<bits/stdc++.h>

typedef long long ll;

int const N = 305 * 2;
int const MOD = 1e9 + 7;

int pa[N];
ll f[N][N];
ll fac[N];
int sum[N];
int n, m;

int main() {
	std::ios::sync_with_stdio(0);
	std::cin >> n >> m;
	fac[0] = 1;
	for(int i = 1; i < N; ++i) if((i & 1) == 0) {
		fac[i] = fac[i - 2] * (i - 1) % MOD;
	}
	for(int i = 1; i <= m; ++i) {
		int x, y;
		std::cin >> x >> y;
		pa[x] = y;
		pa[y] = x;
	}

	n <<= 1;
	for(int i = 1; i <= n; ++i) {
		sum[i] = sum[i - 1];
		if(pa[i] == 0) 
			++sum[i];
	}

	ll ans = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j + i - 1 <= n; ++j) {
			int l = j, r = j + i - 1;
			bool flag = (sum[r] - sum[l - 1]) % 2;
			for(int k = l; k <= r; ++k) if(pa[k]) {
				if(pa[k] < l || pa[k] > r) {
					flag = 1;
					break;
				}
			}
			if(flag) continue;
			f[l][r] = fac[sum[r] - sum[l - 1]];
			for(int k = l; k < r; ++k) {
				int tmp = f[l][k] * fac[sum[r] - sum[k]] % MOD;
				tmp = (MOD - tmp) % MOD;
				f[l][r] = (f[l][r] + tmp) % MOD;
			}
			ans += f[l][r] * fac[n - m - m - (sum[r] - sum[l - 1])] % MOD;
			ans %= MOD;
		}
	}
	std::cout << ans << '\n';
	return 0;
}

Submission Info

Judge Result