AGC028D Chords

,

Description

https://www.luogu.com.cn/problem/AT_agc028_d

Solution

先将圆转化成序列问题。两个直线联通当且仅当序列上的两个区间有交。

容易发现每个联通块的左端点和右端点不存在相交但不包含的情况，不然就联通了。考虑对每一个极大的联通块进行统计出现的方案数，也就是算贡献。记 $f(l,r)$ 表示当前联通块的左端点和右端点分别为 $l,r$ 的方案数，也就是 $l$ 不和左边的任意一个点联通，$r$ 不和其右边的任意点联通，$l,r$ 在同一个联通块内的方案数。记 $c(l,r)$ 表示区间 $[l,r]$ 内还没有被确定的点的数量。$g(i)$ 表示数量为 $i$ 的点配对合法的方案数。

先考虑计算 $g_i$，显然 $i$ 为偶数才有合法方案，且为 $g(i)=(i-1)g(i-2)$。

在不考虑 $l,r$ 两个点联通的情况下，$f(l,r)=g(c(l,r))$。考虑容斥计算 $l,r$ 联通的方案数，有 $f(l,r)=g(c(l,r))-\sum f(l,k)\times g(c(k+1,r))$。

最后对每个区间统计贡献即可。 复杂度 $O(n^3)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 605
#define int long long 
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
ll power(ll x,int y=mod-2,int p=mod) {
	ll sum=1;x%=p;
	while (y) {
		if (y&1) sum=sum*x%p;
		x=x*x%p;y>>=1;
	}
	return sum;
}
int n,k;
int gr[maxn][maxn],gl[maxn][maxn];
int f[maxn][maxn],s[maxn],ans,g[maxn];
void add(int &x,int y) {x=(x+y)%mod;}
signed main(void){
	int i,j,x,y;
	read(n);read(k);
	memset(gr,0x3f,sizeof(gr));
	for (g[2]=1,i=4;i<=2*n;i++) g[i]=g[i-2]*(i-1)%mod;g[0]=1;
	n*=2;
	for (i=1;i<=n;i++) s[i]=1;
	for (i=1;i<=k;i++) {
		read(x),read(y);
		if (x>y) swap(x,y);
		s[x]=0,s[y]=0;
		gl[x][x]=max(gl[x][x],y);
		gr[y][y]=min(gr[y][y],x);
	}
	for (i=1;i<=n;i++) s[i]+=s[i-1];
	for (i=n;i>=1;i--) {
		for (j=i+1;j<=n;j++) {
			gl[i][j]=max(gl[i+1][j],gl[i][j-1]);
			gr[i][j]=min(gr[i+1][j],gr[i][j-1]);
		}
	}
	for (i=n;i>=1;i--) {
		for (j=i+1;j<=n;j++) if (gl[i][j]<=j&&gr[i][j]>=i&&(j-i+1)%2==0) {
			f[i][j]=g[s[j]-s[i-1]];
			for (int k=i;k<j;k++) add(f[i][j],mod-f[i][k]*g[s[j]-s[k]]%mod);
			add(ans,f[i][j]*g[n-2*k-(s[j]-s[i-1])]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i