F - Make Pai（区间dp+计数）
思路：
状态划分： d p [ i ] [ j ] dp[i][j] dp[i][j]为i到j配对完的的方案数
我们让i去找个k配对，那么其中间的一定也要配对完才能选[i+1,k-1],即可 将其划分[i+1,k-1]和[k+1,j]两个集合,然后进行状态转移。
状态转移： d p [ i ] [ j ] = d p [ i + 1 ] [ k − 1 ] ∗ d p [ k + 1 ] [ j ] ∗ C x + y + 1 x dp[i][j]=dp[i+1][k-1]*dp[k+1][j]*C_{x+y+1}^{x} dp[i][j]=dp[i+1][k−1]∗dp[k+1][j]∗Cx+y+1x其中 x = k − i − 1 > > 1 , y = j − k > > 1 x=k-i-1>>1,y=j-k>>1 x=k−i−1>>1,y=j−k>>1。
C j − i + 1 j − k + 1 C_{j-i+1}^{j-k+1} Cj−i+1j−k+1，的意义是两个集合中有x和y+1个配对放x+y+1个位置的方案。
代码：
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=410;
int n,m,e[N][N];
ll f[N][N],fac[2000010];
ll ksm(ll x,ll p){
ll res=1;
while(p){
if(p%2==1) res=res*x%mod;
p/=2;
x=x*x%mod;
}
return res;
}
ll inv(ll a) {
return ksm(a,mod-2)%mod;
}
ll C(ll n,ll k){
if(k>n)return 0;
if(k==1)return n;
return (fac[n]*inv(fac[k])%mod*inv(fac[n-k])%mod);
}
ll dfs(int l,int r){
if(l>r) return 1;
if(f[l][r]!=-1) return f[l][r];
ll ans=0;
for(int i=l+1;i<=r;i+=2){
int x=i-l-1>>1,y=r-i>>1;
if(!e[l][i]) continue;
ans=(ans+1ll*dfs(l+1,i-1)*dfs(i+1,r)%mod*1ll*C(x+y+1,y)%mod)%mod;
}
return f[l][r]=ans;
}
int main(){
cin>>n>>m;
memset(f,-1,sizeof f);
fac[0] = 1;
for(int i = 1;i < 2000006; i++) {
fac[i] = (fac[i-1]*i)%mod;
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
e[u][v]=e[v][u]=1;
}
cout<<dfs(1,2*n)<<"\n";
}