【AGC028D】Chord

「爱情、让人受尽委屈。」 2023-08-17 15:48 92阅读 0赞

# Problem #

## Description ##

给定一个圆，圆上均等地放着 \\(2n\\) 个点，已有 \\(k\\) 对点之间连好了边，从中选择剩下 \\(n-k\\) 对点随意连边。

求所有连边方案中，联通块的个数和。

联通块的定义为：若两对点之间的线段相交，则在一个联通块内。

## Range ##

\\(1\\le k\\le n\\le300\\)

# Algorithm #

\\(DP\\)

# Mentality #

很奇妙的题目。

我们转换成考虑每对点对的贡献。

设 \\(f\_\{i,j\}\\) 表示 \\(i,j\\) 相连，且 \\(i,j\\) 之间的所有点连的边都不与边 \\(i,j\\) 相交的方案数。

则可以考虑用 \\(i,j\\) 之间的点随便连的方案数减去 \\(i,j\\) 不联通的方案数。

考虑枚举一个 \\(i<k<j\\) ，钦定 \\(i,k\\) 相连，然后 \\(k+1,j\\) 之间的点随便连即可。

那么设 \\(g\_i\\) 为 \\(i\\) 个点之间随便连的方案数，则 \\(i\\) 必须为偶数。

设 \\(F(i,j)\\) 为 \\(i,j\\) 之间没有被钦定的点数。

则有：

\\\[ f\_\{i,j\}=g\_\{F(i,j)\} - \\sum\_\{k=i+1\}^\{j-1\} f\_\{i,k\}\*g\_\{F(k+1,j)\} \\\]

那么最后的答案自然为每个点对构成的联通块的贡献：

\\\[ ans=\\sum f\_\{i,j\}\*g\_\{F(1,i-1)+F(j+1,2\*n)\} \\\]

# Code #

#include <algorithm> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <vector> using namespace std; long long read() { long long x = 0, w = 1; char ch = getchar(); while (!isdigit(ch)) w = ch == '-' ? -1 : 1, ch = getchar(); while (isdigit(ch)) { x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); } return x * w; } const int Max_n = 605, mod = 1e9 + 7; int n, K, m, ans; int to[Max_n], s[Max_n]; int f[Max_n][Max_n], g[Max_n]; int F(int l, int r) { if (l > r) return 0; return r - l + 1 - s[r] + s[l - 1]; } int main() { #ifndef ONLINE_JUDGE freopen("D.in", "r", stdin); freopen("D.out", "w", stdout); #endif n = read() << 1, m = read() << 1, g[0] = 1; int u, v; for (int i = 1; i <= (m >> 1); i++) { u = read(), v = read(); to[u] = v, to[v] = u, s[u] = s[v] = 1; } for (int i = 1; i <= n; i++) s[i] += s[i - 1]; for (int i = 2; i <= n; i += 2) g[i] = 1ll * (i - 1) * g[i - 2] % mod; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) if ((j - i) & 1) { bool fl = 0; for (int k = i; k <= j; k++) if (to[k] && (to[k] < i || to[k] > j)) fl = 1; if (fl) continue; f[i][j] = g[F(i, j)]; for (int k = i + 1; k < j; k++) f[i][j] = (f[i][j] - 1ll * f[i][k] * g[F(k + 1, j)] % mod + mod) % mod; ans = (ans + 1ll * f[i][j] * g[F(1, i - 1) + F(j + 1, n)] % mod) % mod; } cout << ans; }

转载于:https://www.cnblogs.com/luoshuitianyi/p/11443459.html