[ABC217F] Make Pair 讲解

zrl123456 · 2024-03-05 21:11:23 · 题解

题目
考察：区间 dp，组合数。

状态与边界条件：

我们设 [l,r] 区间的方案数用 f_{l,r} 表示（1\le l,r\le 2n），那么边界条件就是一个空序列的方案数（即 f_{i+1,i}）的方案数便是 1。

转移方程：

对于每一个 f_{l,r}，若 l 与 r 为朋友关系（我们记作 vis_{l,r}=1），那我们就需要先加上 f_{l+1,r-1}。
接下来我们需要找到一个点（同学）k，把区间 [l,r] 分成两部分，即区间 [l,k-1] 和 [k,r]，然后再将区间 [k,r] 分成 k 点，[k+1,r-1] 区间和 r 点，若 vis_{k,r}=1，则我们需要加上一个数。
就是下面这张图（paint 画图有点丑）：

若只是将 f_{l,k-1} 与 f_{k,r} 相乘，则无法满足题目中对于两种选人的方案，即使同桌关系相同，只要离开队列的顺序不同，也算是不同的方案的条件，那么我们来分析一下：
对于整个 [l,r] 区间需要选 \frac{r-l+1}{2} 次，[k,r] 区间需要选 \frac{r-k+1}{2}，那么我们需要在 \frac{r-l+1}{2} 次中选 \frac{r-k+1}{2} 次，这就是组合数，也就是说这一次的答案是 f_{l,k-1}f_{k+1,r-1}C_{\frac{r-k+1}{2}}^{\frac{r-l+1}{2}}，我们需要提前维护好任意的 C_{i,j}（0\le j\le i\le 2n）。
那么我们得到最后的转移方程：

当然，我们得保证 r-l+1，r-k+1，k-l 均为偶数。
代码：

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define INF 214748364721474836
using namespace std;
inl int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar(x%10^48);
}
#define MOD 998244353
#define N 405
int n,m,u,v,f[N][N],c[N][N];
bool vis[N][N];
signed main(){
    n=read()<<1;
    m=read();
    for(int i=1;i<=m;++i){
        u=read();
        v=read();
        if((u^v)&1) vis[u][v]=vis[v][u]=true;
    }
    for(int i=0;i<=n;++i) f[i+1][i]=1;
    for(int i=0;i<=n;++i)
        for(int j=0;j<=i;++j) 
            if(j==0) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
    for(int len=2;len<=n;len+=2)
        for(int l=1;l+len-1<=n;++l){
            int r=l+len-1;
            if(vis[l][r]) f[l][r]=f[l+1][r-1];
            for(int k=l+2;k<r;k+=2)
                if(vis[k][r]) f[l][r]=(f[l][r]+(f[l][k-1]*f[k+1][r-1]%MOD)*c[len>>1][(r-k+1)>>1]%MOD)%MOD;
        }
    write(f[1][n]%MOD);
    return 0;
}