AOJ 2335: 10歳の動的計画
大学受験のとき使った参考書を引っ張ってきました。
解法
まず寄り道回数のうち左に移動する回数を 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; }