【题解】Chords 计数 dp AGC028D ——quhengyi11

发出可爱的声音.wva

题目大意

给圆圈上的 2n 个点两两连线，事先给你连了 k 对点，让你求连完后的所有方案中的联通块个数之和，联通块的定义是如果两条线交叉那么同属于一个联通块。

Atcoder 的题太妙了

首先我们考虑转换思维，考虑每一个联通块对答案的贡献，我们就能这样设方程

设 $dp[i][j]$表示当前联通块中最小编号为 $i$，最大编号为 $j$的方案数，$[i,j]$里面的点是要全配对过的并且属于当前联通块，那么它对答案的贡献就是 $dp[i][j] \times g[k]$(除去 $[i,j]$和已配对的点还剩 $k$个点，剩下的点随便配对的方案数，记为 $g[k]$)

我们考虑怎么求 $dp[i][j]$

我们可以考虑补集转换，将 $[i,j]$这些点随便连，再减去 $i,j$不配对的方案数就是 $dp[i][j]$

记 $[i,j]$里面有 $f(i,j)$个没有被配对的点，那么我们有

$$dp[i][j] = g[f(i,j)] – \sum_{l = i + 1}^{j – 1} dp[i][l] \times g[f(l + 1, j)]$$
意思就是，如果 $i$和 $l$配对了，那么 $[i,j]$这段联通块的方案数为 $dp[i][l] \times g[f(l + 1, j)]$，减掉所有 $l$的可能情况就行。

顺便如果 $[i,j]$之间有点配对到了这个联通块外面，那么 $dp[i][j] = 0$

代码

#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 605
#define M 4000005
#define mod 1000000007
int n, k, pi[N], x, y, sum[N];
ll g[N], dp[N][N], ans;
inline int f (int x, int y) {return y - x + 1 - (sum[y] - sum[x - 1]);}
int main ()
{
    scanf("%d %d", &n, &k);
    fo (i, 1, k)
    {
        scanf("%d %d", &x, &y);
        pi[x] = y; pi[y] = x;
        sum[x] = 1; sum[y] = 1;
    }
    n <<= 1;
    fo (i, 2, n) sum[i] += sum[i - 1];
    g[0] = 1;
    for (int i = 2; i <= n; i += 2) g[i] = (i - 1) * g[i - 2] % mod;
    fo (i, 1, n)
    {
        fo (j, i, n)
            if ((j - i) & 1)
            {
                bool flag = 0;
                fo (k, i, j)
                    if (pi[k] && pi[k] < i || pi[k] > j)
                    {
                        flag = 1;
                        break;
                    }
                if (flag) continue;
                dp[i][j] = g[f(i, j)];
                fo (k, i + 1, j - 1)
                    dp[i][j] = (dp[i][j] - dp[i][k] * g[f(k + 1, j)]) % mod;
            }
    }
    k <<= 1;
    fo (i, 1, n)
        fo (j, i, n)
            if (dp[i][j])
                ans = (ans + dp[i][j] * g[n - (j - i + 1) - (k - sum[j] + sum[i - 1])]) % mod;
    printf("%lld\n", ans);
    return 0;
}

彩蛋：当 $k=0$的时候，有这个数列