시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 62 27 20 64.516%

문제

방향 그래프 G가 주어졌을 때, 길이가 K보다 작은 서로 다른 사이클의 개수를 구하는 프로그램을 작성하시오. 이 개수는 매우 커질 수 있기 때문에, M으로 나눈 나머지를 출력한다.

사이클은 노드의 연속이며, 같은 노드가 여러 번 등장해도 된다. 이 때, 각각의 노드와 다음 노드 사이에는 간선이 있어야 하며, 마지막 노드와 첫 번째 노드 사이에도 간선이 있어야 한다.

입력

첫째 줄에 그래프 G의 노드의 개수 N, K, M이 주어진다. (1 ≤ N ≤ 35, 1 ≤ K ≤ 106, 1 ≤ M ≤ 109)

둘째 줄부터 N개의 줄에는 그래프의 간선 정보가 인접 행렬 형식 (i번 줄의 j번 문자는 i번 정점과 j번 정점 사이의 간선 정보)로 주어진다. 'Y'는 간선이 있는 것이고, 'N'은 간선이 없는 것이다. 입력으로 주어지는 그래프에 루프는 없다. 즉, i번째 줄의 i번째 문자는 항상 'N'이다.

출력

첫째 줄에 길이가 K보다 작은 서로 다른 사이클의 개수를 M으로 나눈 나머지를 출력한다.

예제 입력 1

4 6 100
NYNY
NNYN
YNNN
YNNN

예제 출력 1

12

예제 입력 2

7 40 13
NYNNNNN
NNYNNNN
NNNYNNN
NNNNYNN
NNNNNYN
NNNNNNY
YNNNNNN

예제 출력 2

9

예제 입력 3

4 1000000 1000000000
NYNY
NNNN
YYNY
NYNN

예제 출력 3

0

예제 입력 4

2 1500 1
NY
YN

예제 출력 4

0

예제 입력 5

7 30 100
NYYNYYN
YNYNYNY
NYNYNYN
YYYNYNY
NNYYNNY
NYYYNNY
YYYYYYN

예제 출력 5

72

예제 입력 6

4 1000 10000
NYYY
YNYY
YYNY
YNYN

예제 출력 6

3564

힌트

예제 1의 경우에 길이가 6보다 작은 사이클은 다음과 같다.

  • (0,3), (3,0), (0,1,2), (1,2,0), (2,0,1), (0,3,0,3), (3,0,3,0), (0,1,2,0,3), (0,3,0,1,2), (1,2,0,3,0), (2,0,3,0,1), (3,0,1,2,0)

출처