페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4763

복잡한 일반항 문제 1s 512MB

문제

1 ≤​ An ≤​ N 범위에서 정의되는 수열 An은 다음과 같이 정의된다.

  • A1 = 1

  • A2 = 2

  • An = B[An-1][An-2] (n ≥ 3)

행렬 B와 K가 주어졌을 때, Ak의 값을 구하여라.​ 


입력

1번 줄 : N K

2번 ~ N + 1번 줄 : B[i][1] B[i][2] ... B[i][N]

제약조건

  • 2 ≤ N ≤ 500

  • 1 ≤ K ≤ 1,000,000,000,000,000,000 (1018)

  • 1 ≤ B[i][j] ≤ N

  • B[i][i] = 0

  • B[i][j] ≠ i​ 


출력

첫 번째 줄에 Ak의 값을 출력하여라.​


예제 #1

2 4

0 2

1 0
2

A1 = 1, A2 = 2, A3 = 1, A4 = 2이다.


예제 #2

4 7

0 4 3 2

4 0 4 1

2 1 0 1

3 2 3 0
3

A1 = 1, A2 = 2, A3 = 4, A4 = 2, A5 = 1, A6 = 4, A7 = 3이다.


출처

COCI 2020 Contest5 #2
로그인해야 코드를 작성할 수 있어요.