ABC 113 D - Number of Amidakuji

• 問題

beta.atcoder.jp

• 解放

DPを使いましょう。
dp[i][j] を上からicm目まで横棒を引いたとき左からj本目の縦棒に行くあみだくじの数とします。
こうするとdp[H][K]が答えになります。
最初は1本目の縦棒にいるのでdp[0][1] = 1です。
正しいあみだくじの条件から、上からi-1cm目のどこかから上からicm目、左からj本目の位置に行けるのは、上からi-1cm目でいた縦棒の位置が左からj-1, j, j+1本目だったときだけです。

つまりdp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]が分かればdp[i][j]を求めることができます。
(i-1,j-1)から(i,j)へ行くときのことを考えてみます。
このときi行目の横線の引き方をMとすると(i-1,j-1)から(i,j)への行き方はdp[i-1][j-1]×Mとなります。
横線の引き方ですが、まず次の3つの条件が成り立たないといけません。

j-1とjの間に横線がある。
j-1とj-2の間に横線はない。
jとj+1の間に横線はない。

この条件からあとは1〜j-2本目までの横線の引き方とj+1〜W本目の横線の引き方を求めればそれらをかけあわせたものがMになります。
そこで縦線がN本のときの横線の引き方の数f(N)を考えます。f(0)=f(1)=1なのは明らかです。f(N)は1本目と2本目の間に線を引いたときの残りの決め方と1本目と2本目の間に線を引かないときの残りの決め方の和になります。前者の場合、2本目と3本目の間に横線があってはいけないので、残りの決め方はf(N-2)通りです。後者の場合はf(N-1)通りです。つまりf(N)=f(N-1)+f(N-2)となりf(N)はフィボナッチ数列のN番目の項に等しくなることがわかります。

ということでM = f(j-2)*f(W-j-1)になります。

他の2つの場合も同様にして求めることでdp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]からdp[i][j]を求めることができます。

#include <iostream>

using namespace std;

typedef long long int ll;

const ll mod = 1e9+7;

int main()
{
	ll h,w,k;
	cin >> h >> w >> k;

	ll fib[10] = {0};
	fib[0] = 1;
	fib[1] = 1;
	for(int i = 2; i < 10; i++){
		fib[i] = fib[i-1]+fib[i-2];
	}

	ll dp[120][10] = {0};

	dp[0][1] = 1;
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(j>1){
				dp[i][j] += dp[i-1][j-1]*fib[j-2]*fib[w-j];
				dp[i][j] %= mod;
			}
			if(j<w){
				dp[i][j] += dp[i-1][j+1]*fib[j-1]*fib[w-j-1];
				dp[i][j] %= mod;
			}

			dp[i][j] += dp[i-1][j]*fib[j-1]*fib[w-j];
			dp[i][j] %= mod;
		}
	}

	cout << dp[h][k] << endl;

	return 0;
}