又被计数题创思力。
Description
Solution
考虑建立图论模型：建立一张包含 \(2n\) 个点的图，将所有 \((A_{2i-1},A_{2i})\) 连边。
首先，考虑一种连边会对应多少种不同的 \(B\)。为方便叙述，我们称 \(x \in [1,2n]\) 被确定，当且仅当 \(x\) 在 \(A\) 中的位置已确定。
显然，若 \(A\) 中只有 \(-1\)，那么可以将所有边的左端点任意排列，有 \(n!\) 种方案，对应 \(n!\) 种不同的 \(B\)。对于一般情况，我们先删去所有两端均确定的边（对于所有满足 \((A_{2i-1},A_{2i})\) 均确定的 \(i\)，将 \(A_{2i-1},A_{2i}\) 两点一同删去），然后将剩余的点重编号，并将边分为两类：
- 两端 \(u,v\) 一者被确定（称其为一类边）。此时，\(\min(u,v)\) 在 \(B\) 中的位置已被确定。
- 两端 \(u,v\) 均未被确定（称其为二类边）。此时，这些 \(\min(u,v)\) 可以在 \(B\) 中任意排列，产生 \(sz!\) 的贡献，其中 \(sz\) 表示这样的 \((u,v)\) 的数量。
注意到 \(sz\) 即为满足 \(A_{2i-1} \neq -1,A_{2i} \neq -1\) 的 \(i(i \in [1,n])\) 的数量，与具体连边无关。最后计算答案时乘上即可。
但答案显然不是连边方案数 \(\times sz!\)，因为可能存在本质相同的连边方案。具体来说，两种连边方案本质不同，当且仅当：
- 所有二类边的左端点组成的可重集不同。
- 存在被确定的 \(x\)，使得包含 \(x\) 的一类边的左端点不同。
现在，我们的任务是：计算本质不同的连边方案数。
考虑从后往前 \(\text{dp}\)，令 \(f_{i,x,y}\) 表示，看了编号 \(\ge i\) 的点，其中有 \(x\) 个被确定的点尚未匹配，有 \(y\) 个未被确定的点尚未匹配。转移考虑如下五种情况：
- \(i-1\) 未被确定
- 匹配一个未被确定的点，相当于在可重集中加入 \(i-1\)，转移到 \(f_{i-1,x-1,y}\)。
- 匹配一个被确定的点，根据之前 \(\lceil\) 本质不同 \(\rfloor\) 的定义，我们关心其另一端的确定点，因此以 \(y\) 的转移系数转移到 \(f_{i-1,x,y-1}\)。
- 暂时不匹配 \(i-1\)，转移到 \(f_{i-1,x,y+1}\)。
- \(i-1\) 被确定。
- 匹配一个未被确定的点，此时以 \(i-1\) 为一端的一类边的左端点必然是 \(i-1\)，我们并不关心其另一端的不确定点，因此直接转移到 \(f_{i-1,x,y-1}\)。
- 匹配一个被确定的点，这是不可能的。
- 暂时不匹配 \(i-1\)，转移到 \(f_{i-1,x+1,y}\)。
边界：\(f_{n+1,0,0}=1\)。
答案：\(f_{1,0,0}\)。
转移是 \(O(1)\) 的，时间复杂度 \(O(n^3)\)，可以通过本题。
Code
#include <bits/stdc++.h>
#define int long long
#define inf 8200000000000000000
using namespace std;
const int N=605,mod=1e9+7;
int read(){
int s=0,w=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') w=-w;ch=getchar();}
while (ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^'0');ch=getchar();}
return s*w;
}
int n,m,sz,ckp[N],f[N][N],g[N][N],vis[N];
void chkadd(int x,int &y){y+=x;if(y>inf)y%=mod;}
void Swap(int &x,int &y){
if (y) y%=mod;
x=y,y=0;
}
signed main(){
n=read();
for (int i=1;i<=n;i++){
int x=read(),y=read();
if (x<0&&y<0) sz++;
else if (x>0&&y>0) vis[x]=vis[y]=2;
else if (x>0) vis[x]=1;
else vis[y]=1;
}
for (int i=1;i<=(n<<1);i++){
if (vis[i]<2) ckp[++m]=i;
}
sort(ckp+1,ckp+m+1,greater<int>()),f[0][0]=1;
for (int t=1;t<=m;t++){
bool typ=vis[ckp[t]];
for (int x=0;x<=min(n,t-1);x++){
for (int y=0,R=min(t-1-x,n);y<=R;y++){
int val=f[x][y];
if (!val) continue;
if (!typ){
if (x) chkadd(val*x,g[x-1][y]);
if (y) chkadd(val,g[x][y-1]);
chkadd(val,g[x][y+1]);
}
else{
if (y) chkadd(val,g[x][y-1]);
chkadd(val,g[x+1][y]);
}
}
}
for (int x=0;x<=min(n,t);x++){
for (int y=0,R=min(t-x,n);y<=R;y++) Swap(f[x][y],g[x][y]);
}
}
int ans=f[0][0];
for (int i=1;i<=sz;i++) ans=(ans*i)%mod;
return cout<<ans,0;
}