１０歳の動的計画 (AOJ 2335) (JAG Summer 2010)

とりあえず縦横を別々に考えられる。よって、縦でx回寄り道して座標Nにいる場合の数をf(x), 横でy回寄り道して座標Mにいる場合の数をg(y)とすると が解である。ここでは縦の移動と横の移動を別々にみたあとにマージするとして、そのマージの仕方の数。N+M+2K回の移動のうち、どのN+2x回の移動を縦の移動に割り当てるかを表す。

問題はf(x), g(y)の求め方になる。

寄り道回数について縦方向の移動で「負の座標を認めて」座標Nまで行く場合の数をF(x)とおくと である。

ここから「負の座標になってしまった」場合の数を取り除いていく。 ちょうど回目の寄り道で「初めて」負の座標-1に到達してしまう時を考えてみよう。 このとき、直前のちょうどz回目の寄り道によって座標0にいるはずである。前進z回、寄り道z回で「負の座標にならずに」座標0にいる場合の数は、いわゆるカタラン数と呼ばれるもので と表すことにする。

「負の座標を認めず座標0」＝＞「一歩後退して座標-1」＝＞「負の座標を認めて座標Nまで移動」

あとは最後の部分を計算する。ちょうどz+1回寄り道したので残りの寄り道回数はx-z-1回。合計N+x-z-1回の移動のうち、x-z-1回寄り道して「負の座標を認めて」座標Nに到達する場合の数はである。

以上により となる。 g(y)も同様に求まる。

namespace comb {
    const int N = 300001;
    mint fact[N];
    mint rev[N];
 
    void init() {
        fact[0] = 1;
        for (int i = 1; i < N; ++i)fact[i] = fact[i - 1] * i;
        for (int i = 0; i < N; ++i)rev[i] = fact[i].inverse();
    }
 
    mint C(int n, int r) {
        if (n < r)return 0;
        return fact[n] * rev[r] * rev[n - r];
    }

    mint catalan(int n) {
        return fact[2 * n] * rev[n + 1] * rev[n];
    }
}
 
int N, M, K;
 
vector<mint> f(int n) {
    vector<mint> res(K + 1);
    rep(i, K + 1) {
        mint x = comb::C(n + 2 * i, i);
        rep(j, i) {
            int k = i - j - 1;
            x -= comb::catalan(j) * comb::C(n + 1 + 2 * k, k);
        }
        res[i] = x;
    }
    RT res;
}
 
int main() {
    comb::init();
 
    cin >> N >> M >> K;
 
    mint ans;
    auto A = f(N);
    auto B = f(M);
    rep(i, K + 1) {
        int j = K - i;
        ans += A[i] * B[j] * comb::C(N + M + K * 2, N + i * 2);
    }
    cout << ans << endl;
}