Submission #4035850


Source Code Expand

#include<iostream>
using namespace std;

#define int long long
#define MOD ((int)1e9+7)
#define MAX_H 110
#define MAX_W 10

int H, W, K;
int amida[MAX_H][MAX_W];

int hoge[MAX_W];

int fuga(int t, int b){
	if(t == W-1) return hoge[t] = 1;
	if(b) return hoge[t] = fuga(t+1,!b);
	else return (hoge[t] = fuga(t+1, b))+fuga(t+1,!b);
}

signed main(){
	
	cin>>H>>W>>K;
	
	fuga(0,1); hoge[W] = 1;

	amida[0][1] = 1;
	
	for(int i = 1; i <= H; i++){
		for(int j = 1; j <= W; j++){
			amida[i][j] = amida[i-1][j]*hoge[j-1]%MOD*hoge[W-j]%MOD + amida[i-1][j-1]*hoge[j-1]%MOD*hoge[W-j+1]%MOD+amida[i-1][j+1]*hoge[j]%MOD*hoge[W-j]%MOD;
			amida[i][j] %= MOD;
		}
	}
	
	cout<<amida[H][K]<<endl;
	
	return 0;
}

Submission Info

Submission Time
Task D - Number of Amidakuji
User Okay
Language C++14 (GCC 5.4.1)
Score 400
Code Size 732 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 6
AC × 16
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt
All in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt
Case Name Status Exec Time Memory
in01.txt AC 1 ms 256 KB
in02.txt AC 1 ms 256 KB
in03.txt AC 1 ms 256 KB
in04.txt AC 1 ms 256 KB
in05.txt AC 1 ms 256 KB
in06.txt AC 1 ms 256 KB
in07.txt AC 1 ms 256 KB
in08.txt AC 1 ms 256 KB
in09.txt AC 1 ms 256 KB
in10.txt AC 1 ms 256 KB
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
sample_05.txt AC 1 ms 256 KB
sample_06.txt AC 1 ms 256 KB