本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$）。
那么我们得到最后的转移方程：
$$f_{l,r}=vis_{l,r}f_{l+1,r-1}+\sum_{k=l+2}^{r-1}vis_{k,r}f_{l,k-1}f_{k+1,r-1}C_{\frac{r-k+1}{2}}^{\frac{r-l+1}{2}}$$ 当然，我们得保证 $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;
}