AOJ 2335: １０歳の動的計画

大学受験のとき使った参考書を引っ張ってきました。

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335

解法

まず寄り道回数のうち左に移動する回数を i 回として横移動と縦移動を分けます。そして, 「横移動の場合の数」と「縦移動の場合の数」および「横移動と縦移動の組み合わせ方の場合の数」を計算して, それを掛けあわせます。
これを 0 <= i <= K のすべての場合について足し合わせたものが答えです。

簡単なところから解いていきます。まず「横移動と縦移動の組み合わせ方の場合の数」ですが, これは 横に移動するのを Y, 縦に移動するのを T とすると,
YYTTYYTTY
みたいな並べ方が何通りあるか, ってやつですね。これはいつものやつで, Y の数が n, T の数が m であるとすると,
通りあります。

問題の主題となるのは「横移動の場合の数」および「縦移動の場合の数」ですね。これはどちらも
「右に移動する回数が p, 左に移動する回数が q で, 常に原点より左側に移動してはならない時, そのような移動の仕方は何通りあるか」という問題に帰着されるので, これの解き方を求めれば良いです(ここで導出される数列はカタラン数と言うらしいです)。

上記の問題を視覚的に書くと以下のようになります。

横軸が「右に移動した回数」で, 縦軸が「左に移動した回数」です。原点より左に移動してはいけないので, (0, 1), (1, 2), ..., (n, n+1) の点を通るのは NG, という意味を込めて対角線のような斜め線 g が入っています。

さて, G に到達する方法は簡単に求めることができるので, G に到達する方法のうち NG な移動の場合の数, すなわち直線 g を通る場合の数を求められれば良いです。これは, 実は G と直線 g に対して対象な点 G' への経路の数と等しいです。これを 1 対 1 対応の観点で示してみましょう。

まず, 原点から G' に移動する方法がそれぞれなんらかの NG な G へ移動する方法と対応することを言います。
原点から G' に移動すると, 必ず直線 g を通るような移動の仕方になります。ここで, 初めて直線 g と交わるような点から先の経路を直線 g に対して対称移動すると, これは NG な G へ移動する経路になります。

次に, NG な G へ移動する方法がそれぞれなんらかの G' に移動する方法と対応することを言います。
NG な G へ移動する方法は, 直線 g を通ります。そこで, 初めて直線 g と交わるような点から先の経路を直線 g に対して対称移動すると, これは G' への経路になります。

以上から, NG な G へ移動する方法と G' に移動する方法が1 対 1 対応であることがわかりました。なので, 単純に G' への経路をいつものように求めれば良いです。

const int MAXN = 100010;
const ll MOD = 1e9+7;
ll fact[3*MAXN], rfact[3*MAXN];

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}
// mod_inverse
ll mod_inverse(ll a, ll m = MOD) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

ll nCr(int n, int r) {
    ll ret = fact[n];
    (ret *= rfact[r]) %= MOD;
    (ret *= rfact[n-r]) %= MOD;
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < 3*MAXN; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
        rfact[i] = mod_inverse(fact[i]);
    }
    int N, M, K;
    cin >> N >> M >> K;
    ll ans = 0;
    int total = N+M+2*K;
    for (int i = 0; i <= K; i++) {
        int yoko = N+2*i;
        int tate = M+2*(K-i);
        ll y = nCr(yoko, i);
        if (i > 0) {
            (y -= nCr(yoko, i-1)) %= MOD;
            if (y < 0) y += MOD;
        }
        ll t = nCr(tate, (K-i));
        if (K-i > 0) {
            (t -= nCr(tate, (K-i)-1)) %= MOD;
            if (t < 0) t += MOD;
        }
        ll plus = (y*t)%MOD;
        (plus *= nCr(total, yoko)) %= MOD;
        ans += plus;
    }
    cout << ans%MOD << endl;
    return 0;
}