Yukicoder No.336 門松列列

solution

DP。$O(N^2)$。

長さ$l$で、 左端がそのひとつ右より$x \in \{ \operatorname{上}, \operatorname{下} \}$で、 右端がそのひとつ左より$y \in \{ \operatorname{上}, \operatorname{下} \}$であるような、門松列列の数を$\operatorname{dp}_{l,x,y}$として更新。 更新は、ふたつの列$l,r$を元にそれらの列の間をそれらの要素の全てより大きい数で繋いで、長さ$|l| + 1 + |r|$の列を作るということを繰り返す。 $\operatorname{dp}_{\operatorname{len}, x, y} \gets \Sigma_{\operatorname{len} = l + 1 + r} \Sigma_{x, y \in \{ \operatorname{上}, \operatorname{下} \}} ( {}_{l+r}C_l \cdot \operatorname{dp}_{l, x, \operatorname{下}} \cdot \operatorname{dp}_{r, \operatorname{上}, y})$。

implementation

#include <iostream>
#include <vector>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors<T, Y, Zs...>(a, y, zs...); return vector<decltype(cont)>(x, cont); }

ll powi(ll x, ll y, ll p) {
    assert (y >= 0);
    x = (x % p + p) % p;
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll inv(ll x, ll p) {
    assert ((x % p + p) % p != 0);
    return powi(x, p-2, p);
}
const int mod = 1000000007;
ll choose(ll n, ll r) { // O(n) at first time, otherwise O(1)
    static vector<ll> fact(1,1);
    static vector<ll> ifact(1,1);
    if (fact.size() <= n) {
        int l = fact.size();
        fact.resize( n + 1);
        ifact.resize(n + 1);
        repeat_from (i,l,n+1) {
            fact[i]  = fact[i-1] * i % mod;
            ifact[i] = inv(fact[i], mod);
        }
    }
    r = min(r, n - r);
    return fact[n] * ifact[n-r] % mod * ifact[r] % mod;
}

const int U = 0;
const int D = 1;
int main() {
    int n; cin >> n;
    vector<vector<vector<ll> > > dp = vectors<ll>(0, n+1, 2, 2);
    if (n == 1 or n == 2) {
        // nop
    } else {
        dp[0][U][D] = 1;
        dp[0][D][U] = 1;
        dp[1][U][U] = 1;
        dp[1][D][D] = 1;
        repeat_from (len,2,n+1) {
            repeat (l,len) {
                int r = len-1 - l;
                assert (l + 1 + r == len and 0 <= l and l < len and 0 <= r and r < len);
                repeat (x,2) repeat (y,2) {
                    dp[len][x][y] += dp[l][x][D] * dp[r][D][y] % mod * choose(l+r, l) % mod;
                }
            }
            repeat (x,2) repeat (y,2) dp[len][x][y] %= mod;
        }
    }
    ll ans = 0;
    repeat (x,2) repeat (y,2) ans += dp[n][x][y];
    cout << (ans % mod) << endl;
    return 0;
}