发出可爱的声音.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$的时候,有这个数列

分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *