AGC028D 题解

First Post:

Last Update:

这题我和王队合力做,王队想到了第一个转化,我想到了第二个转化,但是并没有导出成型的做法,看来,关键时候的坚持确实十分重要。

不要被难度标签所吓到。现在来看,我每次都能隐约想到正解的一些东西,但难出做法,很可能是对算法理解不够深入。

但又该怎么提升呢?也许多做题是有用的。我也能感觉得出来,最近做的题质量有提升。希望这是好的开始。

首先,这题在圆上和在序列上做是没有区别的,两条在圆上相交的线段在序列上也是相交的,反之亦然。

那么,在序列上,线段相当于一段区间,而一堆有交的线段,看上去就像一个大区间。

事实上,对于一个连通块,我们考察其最左边的点 和最右边的点 ,一个连通块显然对应一个区间。

都观察到这里了,我居然想设计一个从前向后的 DP(

看来思考的时候,在草稿纸上写清楚已有的结论至关重要

表示对应区间为 的连通块数,并附加限制:且 中没有点向 之外连边(包括我们所计数的连通块,也包括这个连通块以外,但在 中的点)。

表示 个点任意匹配的方案数,在 为偶数时,其为 ,在 为奇数时其为

表示区间 内还未确定匹配的点数(就是输入中未涉及到的点)。

首先,如果 ,那么

如果读者熟悉图计数的话,会知道一个计数连通块的套路:总方案减去 “ 号点所在连通块大小小于总数” 的方案。

这里也是要计数连通块,我们也还是先让

然后枚举 号点所在连通块不是 的方案数,即

综上所述,有转移式:

最后的答案就是

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
#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 5,P = 1e9 + 7;
int n,K;
int g[N],match[N];
int dp[N][N],sum[N];
inline int Cnt(int l,int r) { return sum[r] - sum[l - 1];}

int main()
{
cin >> n >> K;n <<= 1;
for(int i = 1;i <= K;i++)
{
int u,v;
cin >> u >> v;
match[u] = v;match[v] = u;
}
for(int i = 1;i <= n;i++)
sum[i] = sum[i - 1] + (!match[i]);
g[0] = 1;
for(int i = 2;i <= n;i += 2)
g[i] = 1ll * g[i - 2] * (i - 1) % P;
int ans = 0;
for(int len = 2;len <= n;len += 2)
for(int i = 1;i + len - 1 <= n;i++)
{
int j = i + len - 1,flag = 1;
for(int x = i;x <= j;x++)
if(match[x] && (match[x] < i || match[x] > j)) { flag = 0;break;}
if(!flag) continue;
dp[i][j] = g[Cnt(i,j)];
for(int k = i;k < j;k++)
dp[i][j] = (dp[i][j] + P - 1ll * dp[i][k] * g[Cnt(k + 1,j)] % P) % P;
ans = (ans + 1ll * dp[i][j] * g[n - 2 * K - Cnt(i,j)] % P) % P;
}
cout << ans << endl;
return 0;
}