---

n个人依次坐n把椅子,一个人不会做满足以下条件的椅子

1.这把椅子左右都有椅子

2.这把椅子左右椅子上都有人

3.这把椅子左右椅子颜色不同

问坐满的方案数

当l==r时,根据是否合法返回0或1

其他情况枚举当前坐的椅子位置k

\(dp[l][r]=dp[l][k-1]*dp[k+1][r]*C(k-l,r-l)\)

(左右人坐下的顺序可以交替)

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long LL;const int mod = 1000000007;int n, col[105];int f[105][105];int fact[105], inv[105];void ModAdd(int & x, int y) {    x += y;    if(x >= mod) x -= mod;}int C(int x, int y) {    return (LL)fact[y] * inv[x] % mod * inv[y - x] % mod;}int power(int x, int y) {    int res = 1;    while(y) {        if(y & 1) res = (LL) res * x % mod;        x = (LL) x * x % mod;        y >>= 1;    }    return res;}int DP(int l, int r) {    int lcol = col[l - 1], rcol = col[r + 1];    if(l == r) {        if(lcol == -1 || rcol == -1) return 1;        if(lcol != rcol) return 0;        return 1;    }    int & res = f[l][r];    if(res != -1) return res;    res = 0;    ModAdd(res, DP(l + 1, r));    ModAdd(res, DP(l, r - 1));    for(int i = l + 1; i < r; i++) {        ModAdd(res,         (LL)DP(l, i - 1) * DP(i + 1, r) % mod * C(i - l, r - l) % mod);    }    return res;}int main() {    fact[0] = 1;    for(int i = 1; i <= 100; i++)     fact[i] = (LL) fact[i - 1] * i % mod;    inv[100] = power(fact[100], mod - 2);    for(int i = 99; i >= 0; i--)     inv[i] = (LL) inv[i + 1] * (i + 1) % mod;    while(scanf("%d", &n) != EOF) {        for(int i = 1; i <= n; i++) scanf("%d", &col[i]);        memset(f, -1, sizeof(f));        col[0] = col[n + 1] = -1;        printf("%d\n", DP(1, n));    }    return 0;}