linkkkkk
题意：
有2 ∗ n个数，给出m对关系( a , b )表示a-b有联系。每次将这些数排成一排，如果相邻两个数有联系的话就可以消去，求方案数。
思路：
d p [ l ] [ r ]表示将[ l , r ]之间的数消去的方案数。
枚举中间点k的时候，假设k − r有联系，那么区间就可以分为[ l , k − 1 ] , [ k + 1 , r − 1 ]两段，贡献是
dp[l][k−1]∗dp[k+1][r−1]∗C2r−l+12k−l
如果两个数之间的数的个数是奇数的话，这两个数之间有联系也是对答案没有影响的；同理枚举k kk的时候也要保证分出来的两段区间是偶数个数。
代码：
ll n,m,dp[2100][2100]; bool vis[2100][2100]; vector<int>g[1100]; ll c[2100][2100]; void init(){ for(int i=0;i<2100;i++) for(int j=0;j<=i;j++){ if(j==0) c[i][j]=1; else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } } int main() { init(); n=read,m=read; rep(i,1,m){ int u=read,v=read; if((v-u-1)%2) continue; vis[u][v]=1; if(abs(u-v)==1){ dp[u][v]=dp[v][u]=1; } } for(int len=2;len<=2*n;len+=2){ for(int l=1;l+len-1<=2*n;l++){ int r=l+len-1; if(vis[l][r]) dp[l][r]=dp[l+1][r-1]; for(int k=l+2;k<r;k+=2) if(vis[k][r]){ dp[l][r]=(dp[l][r]+dp[l][k-1]*dp[k+1][r-1]%mod*c[(r-l+1)/2][(k-l)/2]%mod)%mod; } //cout<<dp[l][r]<<endl; } } printf("%lld\n",dp[1][2*n]); return 0; }
