Submission #25629426

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;

mint fac[1000],facinv[1000];
mint mycom(int a,int b){
    if(a-b<0 || b<0)return 0;
    return fac[a]*facinv[b]*facinv[a-b];
}

int n,m;
vector<vector<int>> g;
mint dp[401][401],dp2[401][401];
bool al_dp[401][401],al_dp2[401][401];

mint calc_dp(int i,int j);
mint calc_dp2(int i,int j);

mint calc_dp(int i,int j){
    if(al_dp[i][j])return dp[i][j];
    if(i==j)return 1;
    if(i>j)return 0;
    if((j-i)&1)return 0;
    mint ans=0;
    for(int l=i;l<j;l++){
        ans+=calc_dp(i,l)*mycom((j-i-2)/2,(l-i)/2)*calc_dp2(l,j);
    }
    al_dp[i][j]=true;
    return dp[i][j]=ans;
}
mint calc_dp2(int i,int j){
    if(al_dp2[i][j])return dp2[i][j];
    mint ans=0;
    for(int r:g[i])if(r<j){
        ans+=calc_dp(i+1,r)*calc_dp(r+1,j)*mycom((j-i-2)/2,(j-r-1)/2);
    }
    al_dp2[i][j]=true;
    return dp2[i][j]=ans;
}

int main(){
    fac[0]=facinv[0]=1;
    for(int i=0;i<999;i++){
        fac[i+1]=fac[i]*(i+1);
        facinv[i+1]=facinv[i]/(i+1);
    }

    cin >> n >> m;
    n*=2;
    g.resize(n);
    while(m--){
        int a,b;
        cin >> a >> b;
        a--,b--;
        g[a].emplace_back(b);
    }

    cout << calc_dp(0,n).val() << endl;
}

Submission Info

Judge Result