루미 알고리즘

#1528실버Combination Lock

PO 2021 학교 예선코딩출제 Erik Amirel Eklöf, Fredrik Ekholm, Joakim Blikstad영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Åskold has just bought a new combination lock. The seller promised that the lock is very secure, but Åskold is not convinced. Therefore, he wants you to calculate how many different combinations open the lock.

The code lock consists of N adjacent disks. Each disk has M segments, where a segment is either filled or a hole. To enter a code, you turn the disks. Each disk can be set in M different positions, as the mechanism does not allow you to turn the disk by less than a whole segment. The lock opens if there is at least one hole that goes through all the disks at the same place.

We can describe each disk as a string consisting of ”.” and ”#”, where ”.” represents a segment with a hole and ”#” represents a filled segment. Rotating a disk one step can then be seen as taking the last character of the string and putting it at the beginning. If the disk is rotated M steps, it returns to the position it started in.

For example, the disk ”.#..#” can be set in the following 5 positions:

.#..##.#...#.#...#.##..#.

In total, there are M^N possible ways to set the N disks, and the lock opens if any column consists solely of ”.” when you print all the strings of the disks on top of each other. Write a program that calculates how many different ways there are to set the disks so that the lock opens.

Input

The first line contains integers N, M (1 ≤ N, M ≤ 12), the number of disks and the number of segments.

Then follow N lines, each describing one of the disks. Each disk is described by M characters consisting of ”.” and ”#”.

Output

Print an integer: the number of ways to set the disks so that the lock opens.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

GroupPoint valueConstraints
140M, N ≤ 5
220N ≤ 8, M ≤ 10, and there are at most 3 holes in each disk.
340No additional constraints.

Explanation of samples

• In the first sample, all the nine possible configurations open the lock.

• In the second sample, no configuration will open the lock, as the second disk doesn't have any holes.

• In the third sample, the following two settings open the lock:

.# #.
.# #.
.# #.

• In the fourth sample, there are three (out of the nine possible) settings that do not open the lock: when the ”.” in the second disk is directly under the ”#” in the first disk.

예제

예제 1

입력
2 3
.#.
#..
출력
9

예제 2

입력
3 4
..#.
####
..#.
출력
0

예제 3

입력
3 2
#.
.#
#.
출력
2

예제 4

입력
2 3
..#
.##
출력
6

출처 표기

출처: Programmeringsolympiaden 2021년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.