agc028D

题目大意

n<=300,k<=n

题解

网上的做法全是容斥，这里讲一种直接算的方法

首先显然破环成链，因为如果两边相交则无论在哪里破都相交，不相交则都不相交

那么一个连通块有其点范围[l,r]，并且[l,r]内没有点跑到连通块外去

现在直接枚举[l,r]来计数，计算min在l，max在r的极大连通块个数，并且其中可以包含小连通块（不交且不向外连边），然后乘上外面的情况求和即可

因为现在只算大的，里面小的就作为独立的方案乘到大的里面，再乘上外面的就是当前连通块的总数

设f[i,j]表示当前到i空点有j个，如果当前点是空的则可以连/不连，如果是边的左端点就在右端点时考虑，是右端点就接上唯一对应的左端点，如果超了左边界就break

因为确定的边不能再当作空点，所以在枚举i时另外统计未匹配的左端点个数s

考虑什么时候贡献答案，因为算的是极大连通块，所以要在其独立的瞬间计算，即内部空点j=0（不会往外连）且没有往后连的左端点（s=0）时，并且为了不让其继续往后影响要将其dp值设为0

再处理出g[i]表示i个点的匹配方案即可，时间O(n^3)

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
#define mod 1000000007
#define Mod 1000000005
#define ll long long
//#define file
using namespace std;

ll f[601][601],g[601][601],c[601],ans;
int N,n,m,i,j,k,l,x,y,s;
int a[601];

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}
void init()
{
	g[1][1]=1;c[0]=1;
	fo(i,2,N)
	{
		fo(j,0,n)
		{
			if (j<n) add(g[i][j+1],g[i-1][j]);
			if (j>0) add(g[i][j-1],g[i-1][j]*j);
		}
		if (!(i&1)) c[i/2]=g[i][0];
	}
}

int main()
{
	#ifdef file
	freopen("agc028D.in","r",stdin);
	#endif
	
	scanf("%d%d",&n,&m);N=n*2;
	fo(i,1,m) scanf("%d%d",&x,&y),a[x]=y,a[y]=x;
	init();
	
	fo(i,1,N)
	{
		memset(f,0,sizeof(f));
		if (!a[i]) f[i][1]=1,l=0;
		else
		{
			if (a[i]<i) continue;
			f[i][0]=1,l=1;
		}
		s=0;
		fo(j,i+1,N)
		{
			if (!a[j])
			{
				fo(k,0,n)
				{
					if (k<n) add(f[j][k+1],f[j-1][k]);
					if (k>0) add(f[j][k-1],f[j-1][k]*k);
				}
				if (!l) add(ans,f[j][0]*c[n-(j-i+1)/2-(m-s)]),f[j][0]=0;
			}
			else
			if (j<a[j])
			{
				fo(k,0,n)
				add(f[j][k],f[j-1][k]);
				++l;
			}
			else
			{
				if (a[j]<i) break;
				--l;++s;
				fo(k,0,n)
				add(f[j][k],f[j-1][k]);
				if (!l) add(ans,f[j][0]*c[n-(j-i+1)/2-(m-s)]),f[j][0]=0;
			}
		}
	}
	printf("%lld
",ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}