Submission #1774274

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define N 116
#define mod 1000000007

int n,a[N],f[N][N][N];

void pls(int &x,int y){x=(x+y)%mod;}

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();
	for (int i=1;i<=2*n-1;i++) a[i]=read();
	sort(a+1,a+2*n);a[0]=a[1];a[2*n]=a[2*n-1];
	f[n][a[n]!=a[n-1]][a[n]!=a[n+1]]=1;
	for (int i=n;i>1;i--){
		int l=a[i-2]!=a[i-1],r=a[2*n-i+2]!=a[2*n-i+1];
		for (int j=0;j<=2*n-1;j++)
			for (int k=0;k<=2*n-1;k++)
				if (f[i][j][k]){
					for (int t=0;t<j;t++) pls(f[i-1][t+l][k+r+1],f[i][j][k]);
					pls(f[i-1][j+l][k+r],f[i][j][k]);
					for (int t=0;t<k;t++) pls(f[i-1][j+l+1][t+r],f[i][j][k]);
				}
	}
	int ans=0;
	for (int i=0;i<=2*n-1;i++)
		for (int j=0;j<=2*n-1;j++)
			pls(ans,f[1][i][j]);
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result