Submission #1747232

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define MAXN	55
#define MAXM	105
#define P	1000000007
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int a[MAXM], f[MAXN][MAXM][MAXM];
int cnt[MAXN], smaller[MAXN];
void update(int &x, int y) {
	x = (x + y) % P;
}
int main() {
	int n, m;
	read(n), m = 2 * n - 1;
	for (int i = 1; i <= m; i++)
		read(a[i]);
	sort(a + 1, a + m + 1);
	for (int i = 2; i <= n; i++) {
		if (a[n - i + 1] != a[n - i + 2]) cnt[i] = smaller[i] = 1;
		if (a[n + i - 1] != a[n + i - 2]) cnt[i]++;
	}
	f[1][1][1] = 1;
	for (int i = 1; i < n; i++)
	for (int j = 1; j <= 2 * i - 1; j++)
	for (int k = 1; k <= j; k++) {
		int now = f[i][j][k];
		if (now == 0) continue;
		int goal = j + cnt[i + 1], last = k + smaller[i + 1];
		for (int q = 1; q <= goal; q++)
			if (q == last) update(f[i + 1][goal][q], now);
			else if (q < last) update(f[i + 1][goal - (last - q - 1)][q], now);
			else update(f[i + 1][goal - (q - last - 1)][last + 1], now);
	}
	int ans = 0;
	for (int i = 1; i <= m; i++)
	for (int j = 1; j <= i; j++)
		update(ans, f[n][i][j]);
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result