Submission #3541048


Source Code Expand

Copy
#include <iostream>

using namespace std;

long pow = 1000000007;

long make_pattern(long arg) {
  if (arg <= 1) return 1;
  if (arg == 2) return 2;
  if (arg == 3) return 3;
  if (arg == 4) return 5;
  if (arg == 5) return 8;
  if (arg == 6) return 13;
  if (arg == 7) return 21;
  if (arg == 8) return 39;
  return 0;
}

int main(void) {
  long H, W, K;
  cin >> H >> W >> K;

  long data[H+1][W];
  for (long i = 0; i < H+1; i++) for (long j = 0; j < W; j++) data[i][j] = 0;
  data[0][0] = 1;

  for (long i = 0; i < H; i++) {
    for (long j = 0; j < W; j++) {
      long current = data[i][j];
      if (j > 0) data[i+1][j-1] = (data[i+1][j-1] + current * make_pattern(j - 1) % pow * make_pattern(W - j - 1) % pow) % pow;
      data[i+1][j] = (data[i+1][j] + current * make_pattern(j) % pow * make_pattern(W - j - 1) % pow) % pow;
      if (j < W-1) data[i+1][j+1] = (data[i+1][j+1] + current * make_pattern(j) % pow * make_pattern(W - j - 2) % pow) % pow;
    }
  }

/*
  for (long i = 0; i < H+1; i++) {
    for (long j = 0; j < W; j++) {
      cout << data[i][j] << ", ";
    }
    cout << endl;
  }
*/

  cout << data[H][K-1] << endl;
  return 0;
}

Submission Info

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

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt
All 400 / 400 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 1 ms 256 KB
in02.txt 1 ms 256 KB
in03.txt 1 ms 256 KB
in04.txt 1 ms 256 KB
in05.txt 1 ms 256 KB
in06.txt 1 ms 256 KB
in07.txt 1 ms 256 KB
in08.txt 1 ms 256 KB
in09.txt 1 ms 256 KB
in10.txt 1 ms 256 KB
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sample_04.txt 1 ms 256 KB
sample_05.txt 1 ms 256 KB
sample_06.txt 1 ms 256 KB