# 2018 AtCoder Beginner Contest 113 D - Number of Amidakuji

# Table of Contents

# Problem description

# Problem analysis

Let $A$ be the set of point of Amidakuji. The top of left is $a_{1,1}$ which we start from. The end point is $a_{h,k}$. Assume that matrix $DP$ statisfies the following condition:

$dp_{h,k}$, any element of $DP$, is the number of valid ways from $a_{1,1}$ to $a_{h,k}$.

Our aim is to calculate $dp_{h,k}$.

Let "$\circ$" be $a_{h,k}$. It is observed seen from the following Fig. that there are three ways we can reach $\circ$.

1. $a_{h-1,k-1}$->$a_{h,k-1}$->$a_{h,k}$
2. $a_{h-1,k}$->$a_{h,k}$
3. $a_{h-1,k+a}$->$a_{h,k+1}$->$a_{h,k}$

$\begin{matrix} 1 & \cdots & k-1 & k & k+1 & k+2 & \cdots & w-1 & w \\ \bullet & \cdots & \bullet & \bullet & \bullet & \bullet & \cdots & \bullet & \bullet \\ \bullet & \cdots & \bullet & \bullet & \bullet & \bullet & \cdots & \bullet & \bullet \\ \vdots & & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots \\ \bullet & \cdots & \bullet & \bullet & \bullet & \bullet & \cdots & \bullet & \bullet \\ & & \downarrow & \downarrow & \downarrow & & & & \\ \bullet & \cdots & \bullet & \circ & \bullet & \bullet & \cdots & \bullet & \bullet \end{matrix}$

Without loss of generality, we may cosider case 1. Other cases are almost identical.

$\begin{matrix} & 1 & \cdots & k-2 & k-1 & & k & k+1 & \cdots & w-1 & w \\ 1 & \bullet & \cdots & \bullet & \bullet & & \bullet & \bullet & \cdots & \bullet & \bullet \\ 2 & \bullet & \cdots & \bullet & \bullet & & \bullet & \bullet & \cdots & \bullet & \bullet \\ \vdots & \vdots & & \vdots & \vdots & & \vdots & \vdots & & \vdots & \vdots \\ h-1 & \bullet & \cdots & \bullet & \bullet & & \bullet & \bullet & \cdots & \bullet & \bullet \\ & & & & \downarrow & & & & & & \\ h & \bullet & \cdots & \bullet & \bullet & \rightarrow & \circ & \bullet & \cdots & \bullet & \bullet \end{matrix}$

As it shown in above Fig, we can obtain the number of valid way from $a_{h-1,k-1}$ to $a_{h,k}$ is $F_{k-2}*F_{w-k}*dp_{h-1,k-1}$. $F_{n}$ is the number of Amidakuji with $n$ paralle vertical lines which length is 1cm.

$F_n$ statisfises that $F_{n}=F_{n-2}+F_{n-1}, F_0 = 1, F_1 = 1$. $n$ is non-negative integer. In mathematics, we call the sequence $F_n$ is Fibonacci sequence. The proof of this conclusion is not particulary difficult but will not be reproduced here.

As mentioned above, we have

$dp_{h,k} = dp_{h-1,k-1}*F_{k-2}*F_{w-k} + dp_{h-1,k}*F_{k-1}*F_{w-k} + dp_{h-1,k+1}*F_{k-1}*F_{w-k-1}$

with initial conditions

$dp_{0,0}=1,dp_{0,i}=0,dp_{i,0}=1,i \ge 0, i \in N$

# AC code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF 0xc0c0c0c0
#define NINF 0x3f3f3f3f

#define FOR(i, a, b) for((i)=a; i<b; ++(i))
#define EFOR(i, a, b) for((i)=a; i>b; --(i))

#define MLC(n, type) (type*)malloc(n*sizeof(type))
#define CLC(n, type) (type*)calloc(n, sizeof(type))

#define MAXH 100+2
#define MAXW 8+2
#define MOD(a) ((a)%1000000007)

void calcFibonacci(int *nums, int numsSize, int s, int n1, int n2) {
	int i = 0,tmp;
	int startPoint = s;
	int t1 = n1;
	int t2 = n2;

	nums[startPoint++] = t1;
	nums[startPoint++] = t2;

	FOR(i, startPoint, numsSize) {
		nums[i] = t1+t2;
		tmp = t2;
		t2 = nums[i];
		t1 = tmp;
	}

	// FOR(i, 0, numsSize) {
	// 	printf("%d %d\n", i, nums[i]);
	// }
	// printf("\n");
}

void _solver(long long int *dp, int h, int w, int k) {
	int i,r = 0;
	long long int n1,n2,n3;
	int a[MAXW] = {0};
	calcFibonacci(a, w+1, 0, 1, 1);

	FOR(i, 1, w+1) {
		dp[i] *= a[w-i];
	}

	// FOR(i, 0, w+1) {
	// 	printf("%lld ", dp[i]);
	// }
	// printf("\n");

	FOR(r, 1, h) {
		n1 = dp[1];
		n2 = dp[2];
		n3 = dp[3];

		dp[1] = MOD(dp[1]*a[w-1] + dp[2]*a[w-2]);

		FOR(i, 2, w) {
			dp[i] = MOD(n1*a[w-i]*a[i-2] + n2*a[w-i]*a[i-1] + n3*a[w-i-1]*a[i-1]);
			n1 = n2;
			n2 = n3;
			n3 = dp[i+2];
		}

		dp[i] = MOD(n1*a[i-2] + n2*a[i-1]);

		// FOR(i, 0, w+1) {
		// 	printf("%lld ", dp[i]);
		// }
		// printf("\n");
	}

	printf("%lld\n", dp[k]);
	return;
}

void solver(int h, int w, int k) {
	long long int dp[MAXW] = {0};

	if (k-1 > h) {
		printf("0\n");
		return;
	}
	else if (w == 1) {
		printf("1\n");
		return;
	}

	dp[1] = 1;
	dp[2] = 1;

	_solver(dp, h, w, k);
}

int main() {
	int h,w,k;

	scanf("%d %d %d", &h, &w, &k);
	solver(h, w, k);

	return 0;
}