Submission #5970874


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 610;
const int mod = 1e9 + 7;
long long dp[maxn][maxn] = {0}, g[maxn], h[maxn][maxn];
int ea[maxn], eb[maxn];
int n, m;
bool in(int l, int r, int x)
{
	return l <= x && x <= r;
}
int get(int l, int r)
{
	int cnt = 0;
	for(int i = 1; i <= m; i ++)
	{
		bool asd1 = in(l, r, ea[i]), asd2 = in(l, r, eb[i]);
		if(asd1 ^ asd2)
			return -1;
		if(asd1)
			cnt ++;
	}
	return cnt * 2;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin >> n >> m;
	n *= 2;
	for(int i = 1; i <= m; i ++)
		cin >> ea[i] >> eb[i];
	g[0] = 1;
	for(int i = 2; i <= n; i += 2)
		g[i] = g[i - 2] * (i - 1) % mod;
	for(int i = 1; i <= n; i ++)
		for(int j = i; j <= n; j ++)
			h[i][j] = get(i, j);
	long long ans = 0;
	for(int l = 2; l <= n; l += 2)
		for(int i = 1; i + l - 1 <= n; i ++)
		{
			int j = i + l - 1;
			//cout << i << " " << j << " : " << endl;
			int c = h[i][j];
			//cout << c << endl;
			if(c != -1)
			{
				long long a = g[n - l - m * 2 + c];
				dp[i][j] = g[l - c] % mod;
				//cout << g[l - c] << " " << a << endl;
				for(int k = i + 1; k < j; k += 2)
					if(h[k + 1][j] != -1 && h[i][k] != -1)
					{
						(dp[i][j] += (mod - dp[i][k] * g[j - k - h[k + 1][j]] % mod)) %= mod;
						//cout << k << " " << dp[i][k] << " " << j - k - h[k + 1][j] << " " << g[j - k - 1 - h[k + 1][j]] << endl;
						//cout << dp[i][k] * g[j - k - 1 - h[k + 1][j]] % mod * a % mod << endl;
					}
				(ans += dp[i][j] * a) %= mod;
			}
			//cout << dp[i][j] << endl;
		}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Chords
User zhangyuxi
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1705 Byte
Status
Exec Time 104 ms
Memory 6016 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
All 900 / 900 sample-01.txt, sample-02.txt, sample-03.txt, sample-01.txt, sample-02.txt, sample-03.txt, subtask01-01.txt, subtask01-02.txt, subtask01-03.txt, subtask01-04.txt, subtask01-05.txt, subtask01-06.txt, subtask01-07.txt, subtask01-08.txt, subtask01-09.txt, subtask01-10.txt, subtask01-11.txt, subtask01-12.txt, subtask01-13.txt, subtask01-14.txt, subtask01-15.txt, subtask01-16.txt, subtask01-17.txt, subtask01-18.txt, subtask01-19.txt, subtask01-20.txt
Case Name Status Exec Time Memory
sample-01.txt 2 ms 2304 KB
sample-02.txt 2 ms 2304 KB
sample-03.txt 2 ms 2432 KB
subtask01-01.txt 2 ms 2304 KB
subtask01-02.txt 57 ms 5760 KB
subtask01-03.txt 35 ms 5632 KB
subtask01-04.txt 2 ms 3072 KB
subtask01-05.txt 2 ms 2816 KB
subtask01-06.txt 18 ms 5376 KB
subtask01-07.txt 5 ms 4096 KB
subtask01-08.txt 4 ms 3456 KB
subtask01-09.txt 78 ms 6016 KB
subtask01-10.txt 15 ms 5888 KB
subtask01-11.txt 5 ms 5632 KB
subtask01-12.txt 5 ms 4864 KB
subtask01-13.txt 5 ms 4480 KB
subtask01-14.txt 5 ms 4352 KB
subtask01-15.txt 6 ms 5760 KB
subtask01-16.txt 9 ms 5632 KB
subtask01-17.txt 22 ms 5504 KB
subtask01-18.txt 28 ms 4864 KB
subtask01-19.txt 58 ms 4992 KB
subtask01-20.txt 104 ms 5248 KB