별자리 탐험대
골드 IV의견: 0
우주 탐험 게임 '별자리 탐험대'에는 \(N\)개의 별(노드 \(1\)번 ~ \(N\)번)과 별들을 연결하는 단방향 항로(간선)가 있다. 자기 자신으로 가는 항로가 있을 수도 있고, 두 별 사이에 항로가 없거나 하나 있다.
탐험대는 정확히 \(K\)번 이동해야 한다. 이동할 때마다 현재 별에서 나가는 항로 중 하나를 선택해 이동한다.
별 \(i\)에서 출발해 정확히 \(K\)번 이동하여 별 \(j\)에 도착하는 경로의 수를 \(10^9 + 7\)로 나눈 나머지를 모든 쌍 \((i, j)\)에 대해 출력하여라.
- \(1 \le N \le 8\)
- \(0 \le K \le 10^{18}\)
- 인접 행렬의 각 원소는 \(0\) 또는 \(1\)이다.
첫째 줄에 별의 수 \(N\)과 이동 횟수 \(K\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 걸쳐 인접 행렬이 주어진다. \(i\)번째 줄의 \(j\)번째 값이 \(1\)이면 별 \(i\)에서 별 \(j\)로 가는 항로가 있음을, \(0\)이면 없음을 나타낸다.
\(N\)개의 줄에 걸쳐 결과 행렬 \(A^K\)를 출력한다. \(i\)번째 줄의 \(j\)번째 값은 별 \(i\)에서 출발해 정확히 \(K\)번 이동하여 별 \(j\)에 도착하는 경로의 수를 \(10^9 + 7\)로 나눈 나머지이다.
3 3
0 1 0
0 0 1
1 0 0
1 0 0
0 1 0
0 0 1
길이 \(3\)인 사이클이므로 각 별자리는 정확히 \(3\)걸음 후 자기 자신으로 돌아온다. 따라서 \(A^3\)은 단위 행렬이다.
2 2
1 1
1 1
2 2
2 2
두 노드가 서로 완전히 연결되어 있으므로 길이 \(2\)의 경로는 각 쌍 사이에 \(2\)가지 (자기-자기-도착 또는 상대-자기-도착) 가 있다.
riseoj 작성
출처 Original
평가 및 의견
별자리 탐험대
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
별자리 탐험대