题目大意

　　有一个长度为序列 \(a\)，其中某些位置的值是 \(-1\)。

　　你要把 \(a\) 补成一个排列。

　　定义 \(b_i=\min(a_{2i-1},a_{2i})\)，求有多少种可能的 \(b\)。

　　\(n\leq 300\)

题解

　　如果 \(a_{2i-1}\) 和 \(a_{2i}\) 都有值，就把这两个位置扔掉。

　　记 \(c_i\) 表示 \(i\) 这个值是否在初始的 \(a\) 中。

　　从后往前DP。记 \(f_{i,j,k}\) 表示已经处理完了 \(i\) 后面的数，有多少个 \(j>i,c_j=1\) 的数匹配的是 \(\leq i\) 的数，有多少个 \(j>i,c_j=0\) 的数匹配的是 \(\leq i\) 的数。

　　如果 \(c_i=1\) 且往后匹配的是 \(c_j=0\)，那么方案数为 \(1\)。（因为 \(\min=i\)）

　　如果 \(c_i=0\) 且往后匹配的是 \(c_j=0\)，那么先暂定方案数为 \(1\)。（因为暂时不能确定 \(i\) 填在哪个位置。）记这种匹配对数为 \(cnt\)。

　　如果 \(c_i=0\) 且往后匹配的是 \(c_j=1\)，那么方案数为 \(j\)。（因为可以确定 \(i\) 填在哪个位置。）

　　最后方案数要乘上 \(cnt!\)，因为这些位置的 \(b\) 可以随便交换。

　　时间复杂度：\(O(n^3)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<functional>

#include<cmath>

#include<vector>

#include<assert.h>

//using namespace std;

using std::min;

using std::max;

using std::swap;

using std::sort;

using std::reverse;

using std::random_shuffle;

using std::lower_bound;

using std::upper_bound;

using std::unique;

using std::vector;

typedef long long ll;

typedef unsigned long long ull;

typedef double db;

typedef std::pair<int,int> pii;

typedef std::pair<ll,ll> pll;

void open(const char *s){

#ifndef ONLINE_JUDGE

	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);

#endif

}

void open2(const char *s){

#ifdef DEBUG

	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);

#endif

}

int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}

void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}

int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}

int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}

const ll p=1000000007;

const int N=310;

void add(ll &a,ll b)

{

	a=(a+b)%p;

}

int n;

int a[2*N];

ll f[2*N][N][N];

int b[2*N];

int c[2*N];

int t;

int main()

{

	open2("f");

	scanf("%d",&n);

	for(int i=1;i<=2*n;i++)

		scanf("%d",&a[i]);

	int cnt=0;

	for(int i=1;i<=2*n;i+=2)

		if(a[i]!=-1&&a[i+1]!=-1)

			b[a[i]]=b[a[i+1]]=2;

		else if(a[i]!=-1)

			b[a[i]]=1;

		else if(a[i+1]!=-1)

			b[a[i+1]]=1;

		else

			cnt++;

	for(int i=1;i<=2*n;i++)

		if(b[i]==1)

			c[++t]=1;

		else if(b[i]==0)

			c[++t]=2;

	f[t][0][0]=1;

	for(int i=t;i>=1;i--)

		for(int j=0;j<=t&&j<=n;j++)

			for(int k=0;k<=t&&k<=n;k++)

				if(c[i]==1)

				{

					add(f[i-1][j+1][k],f[i][j][k]);

					if(k)

					 	add(f[i-1][j][k-1],f[i][j][k]);

				}

				else

				{

					add(f[i-1][j][k+1],f[i][j][k]);

					if(k)

						add(f[i-1][j][k-1],f[i][j][k]);

					if(j)

						add(f[i-1][j-1][k],f[i][j][k]*j);

				}

	ll ans=f[0][0][0];

	for(int i=1;i<=cnt;i++)

		ans=ans*i%p;

	printf("%lld\n",ans);

	return 0;

}