AT4438 - Chords

题意

给定一个圆, 圆上均等地放着 2×N2\times N 个点, 已有 KK 对点之间连好了线段, 从中选择剩下 N−KN−K 对点随意连线段(每个点只连一条线段).

两点联通当且仅当两点在同一条线段上或两点所属于的线段相交, 求所有连边方案中, 联通块的个数和.

1≤N≤300,0≤K≤N1\le N\le 300,0\le K\le N

题解

首先考虑把圆转化的序列上，圆上线段相交  ⟺  \iff序列上两区间有交但不包含 。

考虑计算每个连通块对答案的贡献，就是每个连通块出现的方案数。

定义：
g(x)g(x) 表示 xx 个点随意连的方案数，显然：

g(x)={∏i=1x/2(2i−1)if x is even0otherwiseg(x)= \begin{cases} \prod_{i=1}^{x/2} (2i-1) & \text{if x is even}\\ 0 &\text{otherwise} \end{cases}

c(i,j)c(i,j) 表区间 [i,j][i,j] 内剩余没匹配的点数。如果区间 [i,j][i,j] 随便连就是 g(c(i,j))g(c(i,j)) ，就是每个点随意钦定一个对点。

dp[i][j]dp[i][j] 表示 [i,j][i,j] 区间构成连通块的方案数，满足不存在区间 [i,j][i,j] 里的点向外面连边，且 i,ji,j 属于同一个连通块 （但可以在其内部有其他小的连通块）。答案应该就是 ∑i,jdp[i][j]×g(c(1,i−1)+c(j+1,n))\sum_{i,j} dp[i][j]\times g(c(1,i-1)+c(j+1,n)) 。（ 因为是计算每种连通块出现的次数，[i,j][i,j] 之外的连法不同也要记录在内 ）

现在考虑计算 dp[i][j]dp[i][j] ： 要满足 i,ji,j 属于同一个连通块，简单容斥，总数量减去不合法的，总数量就是 [i,j][i,j] 内任意连边，对于不合法的情况，我们钦定 ii 连到 k∈(i,j)k\in(i,j) ，且 >k\gt k 的点不会连到 [l,k][l,k] ， 那就是 dp[i][k]×g(c(k+1,j))dp[i][k]\times g\left(c(k+1,j)\right) （ 左边合法 [i,k][i,k] 保证不会有点连向右边，右边不干扰左边乱连即可，保证不重不漏 ）

dp[i][j]=g(c(i,j))−∑k=i+1j−1dp[i][k]×g(c(k+1,j))dp[i][j]=g\left(c(i,j)\right) -\sum_{k=i+1}^{j-1} dp[i][k]\times g\left(c(k+1,j)\right)

复杂度 O(n3)O(n^3)

CODE

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
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void red(T &x) {
    x=0;bool fg=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
    if(fg) x=-x;
}
const int N = 605;
const int mod = 1e9+7;
typedef long long ll;
ll dp[N][N],ct[N],g[N]={1};
int n,K,p[N];
int c(int l,int r) {return r-l+1-(ct[r]-ct[l-1]);}
int main() {
    red(n);red(K);n*=2;
    for(int i=2;i<=n;i+=2) g[i]=1ll*g[i-2]*(i-1)%mod;
    for(int i=1;i<=K;i++) {
        int a,b;red(a);red(b);
        p[a]=b;p[b]=a;
        ct[a]++;ct[b]++;
    }   
    for(int i=1;i<=n;i++) ct[i]+=ct[i-1];
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            if((j-i+1)&1) continue;
            bool fg=0;
            for(int k=i;k<=j;k++) {
                if(p[k]!=0&&p[k]<i||p[k]>j) {fg=1;break;}
            }
            if(fg) continue;
            dp[i][j]=g[c(i,j)];
            for(int k=i+1;k<j;k++) {
                dp[i][j]-=dp[i][k]*g[c(k+1,j)]%mod;
                dp[i][j]%=mod;
                if(dp[i][j]<0) dp[i][j]+=mod;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            ans+=dp[i][j]*g[c(1,n)-c(i,j)];
            ans%=mod;
        }
    }
    printf("%lld\n",ans);
}