不过求ggg不用O(n2)DPO(n^2)DPO(n2)DP，g[n]g[n]g[n]直接就是卡特兰数的第n−1n-1n−1项。即：

g[n]=(2(n−1)n−1)−(2(n−1)n−2)g[n]=\binom{2(n-1)}{n-1}-\binom{2(n-1)}{n-2}g[n]=(n−12(n−1))−(n−22(n−1))

相当于在平面直角坐标系中，要从(0,0)(0,0)(0,0)走到(n,n)(n,n)(n,n)，有一条线段y=x(x∈(0,n))y=x(x\in(0,n))y=x(x∈(0,n))不能触碰，注意是开区间。所以卡特兰数/组合数的计算方法就行了。

CODE

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 105;

int n, mod, g[MAXN], f[MAXN][MAXN][MAXN], fac[MAXN<<1], inv[MAXN<<1];

int C(int n, int m) { return m > n ? 0 : 1ll * fac[n] * inv[m] % mod * inv[n-m] % mod; }

int main(){

    scanf("%d%d", &n, &mod);

    fac[0] = inv[0] = inv[1] = fac[1] = 1;

    for(int i = 2; i <= (n<<1); ++i){

        fac[i] = 1ll * fac[i-1] * i %mod;

        inv[i] = 1ll * (mod - mod/i) * inv[mod%i] % mod;

    }

	for(int i = 2; i <= (n<<1); ++i) inv[i] = 1ll * inv[i-1] * inv[i] % mod;

    for(int i = 1; i <= n; ++i) g[i] = C(2*i - 2, i - 1) - C(2*i - 2, i - 2);

    f[0][0][0] = 1;

    for(int i = 0; i <= n; ++i)

        for(int j = 0; j <= n; ++j) if(i || j) {

            for(int k = max(0, i+j-n); k <= i && k <= j; ++k){

                int &ret = f[i][j][k];

                if(i && k) ret = (ret + 1ll * f[i-1][j][k-1] * (j-k+1)) % mod;

                if(j && k) ret = (ret + 1ll * f[i][j-1][k-1] * (i-k+1)) % mod;

                if(i) ret = (ret + 1ll * f[i-1][j][k] * (n - (i-1+j-k))) % mod;

                if(j) ret = (ret + 1ll * f[i][j-1][k] * (n - (i+j-1-k))) % mod;

                for(int d = 1; d <= k; ++d)

                    ret = (ret - 1ll * f[i-d][j-d][k-d] * C(n-(i+j-k-d), d) % mod * g[d] % mod * fac[d] % mod) % mod;

            }

        }

    printf("%d\n", (f[n][n][n] + mod) % mod);

}

没做过这种类型的感觉好难。。

1N

51nod 1843 排列合并机（DP+组合）

CODE