시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 11 8 8 72.727%

문제

그래프 G에서 길이 L ≥ 3인 단순 사이클이란 정점 순열 (v0, v1, ..., vL-1)을 말한다. 이때, v0, v1, ..., vL-1은 모두 같지 않아야 하고, 모든 0 ≤ i ≤ L-1에 대해서, vi와 vi+1 mod L 를 연결하는 간선이 G에 있어야 한다.

두 트리를 연결해서 그래프를 만들 수 있다. 트리의 연결은 다음과 같은 과정을 거친다.

먼저, 두 트리는 모두 N개의 정점으로 이루어져 있고, 정점은 0번부터 N-1번까지 번호가 매겨져 있다. 이제, 0부터 N-1까지 수로 이루어진 순열 P를 하나 만든다. 그 다음, 모든 0 ≤ i ≤ N-1에 대해서, 첫 번째 트리에서 i번 정점과, 두 번째 트리에서 P[i]번째 정점을 연결한다.

이렇게 만든 그래프에서 원래 첫 번째 트리에 있던 i번 정점은 Ai로, 두 번째 트리에 있던 i번 정점은 Bi로 나타낸다.

P를 어떻게 고르냐에 따라서, 나올 수 있는 길이가 K인 단순 사이클의 개수는 달라진다.

두 트리와 K가 주어졌을 때, P를 길이가 K인 단순 사이클의 개수가 가장 크게 되게 골랐을 때, 단순 사이클의 개수를 구하는 프로그램을 작성하시오.

두 단순 사이클 X와 Y가 있을 때, X를 쉬프트하거나, 뒤집어서 쉬프트했을 때, Y를 만들 수 있다면, X와 Y는 같은 사이클이다. 예를 들어, (1, 2, 3, 4), (2, 3, 4, 1), (3, 2, 1, 4)는 모두 같은 사이클이다.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 9, 3 ≤ K ≤ 7)

둘째 줄부터 N개의 줄에 트리 1의 정보가, 다음 N개의 줄에 트리 2의 정보가 주어진다. 트리의 정보는 인접 행렬로 주어지며, '-'인 경우에는 간선이 없음, 'X'인 경우는 간선이 있음을 나타낸다.

출력

첫째 줄에 입력으로 주어진 두 트리를 연결했을 때 나올 수 있는 길이가 K인 단순 사이클의 최대 개수를 출력한다.

예제 입력 1

2 4
-X
X-
-X
X-

예제 출력 1

1

예제 입력 2

3 5
-X-
X-X
-X-
-X-
X-X
-X-

예제 출력 2

2

예제 입력 3

3 3
-X-
X-X
-X-
-X-
X-X
-X-

예제 출력 3

0

예제 입력 4

5 6
-X---
X-XXX
-X---
-X---
-X---
-X-X-
X-X-X
-X---
X----
-X---

예제 출력 4

5

힌트

예제 1의 경우에 두 방법으로 합칠 수 있고, 길이가 4인 단순 사이클은 1개이다.

예제 2의 경우에는 총 6가지 방법으로 합칠 수 있다.

가장 위에 있는 두 그래프를 제외하면 길이가 5인 단순 사이클을 총 2개씩 갖는다.

예제 3은 예제 2와 같은 그래프이다. 길이가 3인 사이클은 없다.

예제 4의 경우에 정답 P = [0, 3, 2, 1, 4] 이다. 길이가 6인 단순 사이클 5개를 찾을 수 있다.

  • A0, A1, A4, B4, B1, B0
  • A0, A1, A2, B2, B1, B0
  • A1, A2, B2, B1, B0, B3
  • A1, A2, B2, B1, B4, A4
  • A1, A4, B4, B1, B0, B3

출처

  • 문제의 오타를 찾은 사람: jh05013