#P3250. Light Switches
Light Switches
Problem Background
In Minecraft, there are many cute creatures like Creepers and different types of zombies. When you don't have enough equipment, the only option when encountering them is to run away. To prevent them from exploding near the house you worked hard to build, you decide to explore the nearby terrain and design some detour routes to deal with multiple monsters.
Problem Description
Given a directed graph where the length of all edges is 1, calculate the number of cycles with a total length less than , and return the result modulo .
Note that the definition of "different cycles" is crucial, so please refer to the examples for clarification. It is guaranteed that the graph does not have self-loops (i.e., for all , ).
Input Format
The first line contains an integer , representing the number of nodes in the graph.
The next lines each contain a string of length . In each string:
- If , it means there is a directed edge from node to node ;
- If , it means there is no edge from node to node .
The last line contains two integers and .
Input constraints:
Output Format
Output a single integer representing the number of cycles with a total length less than , modulo .
Example
Input Example:
4
NYNY
NNYN
YNNN
YNNN
6 100
Output Example:
12
Explanation: There are 12 distinct cycles as follows:
- Cycles of length 2:
- Cycles of length 3:
- Cycles of length 4:
- Cycles of length 5: $(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)$
Notes
- Pay special attention that cycles cannot have self-loops (i.e., holds for all ).
- The order in which the nodes are traversed in the cycle is important for distinguishing different cycles, as shown in the example where multiple distinct solutions are listed.