首先我们考虑转换思维,考虑每一个联通块对答案的贡献。
设 (f[i][j]) 表示当前联通块中最小编号为 (i),最大编号为 (j) 的方案数,(i) 到 (j) 里面的点是要全连过边的并且没有连出去块的边,而且(i) 和 (j) 相连,那么它对答案的贡献就是 (除去 ([i,j]) 和已配对的点还剩 (x) 个点,剩下的点随便配对的方案数,记为 (g[x])) 。
我们考虑 (f[i][j]) 怎么求 。考虑用总数减去不合法的,将 ([i,j]) 这些点在块内随便连,再减去 (i) 和 (j) 不配对的方案数就是 (f[i][j]) 。记 ([i,j]) 里面有 (h(i,j)) 个没有被配对的点,那么我们有
[f[i][j]=g[h(i,j)]-sum_{l=i+1}^{j-1}f[i][l]*g[h(l+1,j)]
]
意思就是,如果 (i) 和 (l) 连边了,那么 ([i,j]) 这段联通块的方案数为 (f[i][l]*g[h(l+1,j)]) ,减掉所有 (l) 的可能情况就行了。 顺便说一下如果 ([i,j]) 之间有点配对到了这个联通块外面,那么 (f[i][j]=0) 。
附上代码
#include<cstdio>
using namespace std;
const int N=605,mo=1e9+7;
int a[N],f[N][N],g[N],s[N];
int n,m,mi,ma,an,i,j,k,x,y;
int main(){
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
scanf("%d%d",&n,&m); n*=2;
for(i=1;i<=m;++i)
scanf("%d%d",&x,&y),a[x]=y,a[y]=x,s[x]=s[y]=1;
for(i=1;i<=n;++i){
if (!a[i]) a[i]=i;
s[i]+=s[i-1];
}
g[0]=1;
for(i=2;i<=n;i+=2)
g[i]=1ll*g[i-2]*(i-1)%mo;
for(i=1;i<=n;++i){
mi=ma=a[i];
for(j=i+1;j<=n;++j){
if (a[j]<mi) mi=a[j];
if (a[j]>ma) ma=a[j];
if (mi<i||ma>j) continue;
x=j-i+1-s[j]+s[i-1];
f[i][j]=g[x];
if (!g[x]) continue;
for(k=i+1;k<j;++k)
f[i][j]=(-1ll*f[i][k]*g[j-k-s[j]+s[k]]%mo+f[i][j]+mo)%mo;
an=(an+1ll*f[i][j]*g[n-s[n]-x])%mo;
}
}
printf("%d",an);
return 0;
}