题目

有一个圆,圆上均匀分布着 $2n$ 个点,将点两两匹配,并给匹配的点连接一条线段,定义两个点连通当且仅当它们可以只通过连接的线段和线段之间的交点走到对方。

已经匹配好了 $m$ 对点,求所有将剩下 $2(n - m)$ 个点匹配的方案的连通块个数之和,对 $10^9 + 7$ 取模。

$1\le m\le n\le 300$.

分析

显然在圆上和在一个弧上连出来的效果是一样的。

设 $f_{i,j}$ 表示将 $i,j$ 连到一个连通块中,且 $i,j$ 分别为这个连通块中编号最小和最大的点,只考虑 $[i,j]$ 这部分点的方案数。

再设 $g_i$ 表示将 $i$ 个点两两连边的方案数,显然有:

$$ g_i = \prod_{0\le 2j\le i} (i-2j) $$

再记 $\operatorname{cnt}(i,j)$ 表示 $[i,j]$ 中还未确定连边的点数,则显然答案为:

$$ \sum_{1\le i\le j\le n} f_{i,j}\cdot g_{n-2m+\operatorname{cnt}(i,j)} $$

对于如何求 $f_{i,j}$,考虑显然区间内外不能连边,所以若区间内存在连向区间外的边,则 $f_{i,j} = 0$.

否则考虑先随便连边,这部分的方案数是 $g_{\operatorname{cnt}(i,j)}$,注意到这样 $i,j$ 不一定会被连到一个连通块中,但 $i$ 一定属于某个连通块,考虑枚举这个连通块的右端点为 $k$,则有:

$$ f_{i,j} = g_{\operatorname{cnt}(i,j)} - \sum_{i\le k<j} f_{i,k}\cdot g_{\operatorname{cnt}(k+1,j)} $$

然后就做完了,时间复杂度 $\mathcal O(n^3)$.

代码

const int kN = 6e2 + 5;
const ll kMod = 1e9 + 7;

int n, m, t[kN]; ll f[kN][kN], c[kN][kN], g[kN];
int main() { 
    rd(n, m); n *= 2;
    for(int i = 1; i <= m; ++i) {
        int u, v; rd(u, v);
        t[u] = v; t[v] = u;
    }
    g[0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = i; j <= n; ++j)
            c[i][j] = c[i][j - 1] + (t[j] == 0);
        g[i] = 1;
        for(int j = i - 1; j >= 0; j -= 2)
            g[i] = g[i] * j % kMod;
    }
    for(int len = 1; len <= n; len += 2) {
        for(int i = 1; i + len <= n; ++i) {
            int j = i + len; bool flag = true;
            for(int k = i; k <= j; ++k)
                if(t[k] && (t[k] > j || t[k] < i))
                    flag = false;
            if(flag) {
                f[i][j] = g[c[i][j]];
                for(int k = i; k < j; ++k)
                    f[i][j] = (f[i][j] - f[i][k] * g[c[k + 1][j]] % kMod + kMod) % kMod;
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            ans = (ans + f[i][j] * g[n - 2 * m - c[i][j]]) % kMod;
    printf("%lld\n", ans);
    return 0;
}
最后修改:2021 年 03 月 14 日 05 : 13 PM