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 |
|
|
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 |