영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Point value | Constraints |
|---|---|---|
| 1 | 40 | M, N ≤ 5 |
| 2 | 20 | N ≤ 8, M ≤ 10, and there are at most 3 holes in each disk. |
| 3 | 40 | No 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