Submission #1607152

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int dp[55][105][105],n,a[105],ret;
int main(){
	cin>>n;
	for(int i=1;i<=2*n-1;i++) cin>>a[i];
	sort(a+1,a+2*n);
	dp[n][1][1] = 1;
	for(int i=n;i>=1;i--){
		for(int j=1;j<=2*n-1;j++){
			for(int k=1;k<=j;k++){
				if(i==1) ret=(ret+dp[i][j][k])%mod;
				if(dp[i][j][k] == 0) continue;
				int L = (a[i] != a[i-1]);
				int R = (a[2*n-i] != a[2*n-i+1]);
				if(L){
					dp[i-1][j+L+R-(k-1)][1] += dp[i][j][k];
					dp[i-1][j+L+R-(k-1)][1] %= mod;
				}
				if(R){
					dp[i-1][j+L+R-(j-k)][j+L+R-(j-k)] += dp[i][j][k];
					dp[i-1][j+L+R-(j-k)][j+L+R-(j-k)] %= mod;
				}
				for(int x=1;x<=j;x++){
					dp[i-1][j+L+R-max(0,abs(x-k)-1)][(x>k?L+k+1:L+x)] += dp[i][j][k];
					dp[i-1][j+L+R-max(0,abs(x-k)-1)][(x>k?L+k+1:L+x)] %= mod;
				}
			}
		}
	}
	cout<<ret<<endl;
}

Submission Info

Judge Result