2079. TourCounting

单点时限: 10.0 sec

内存限制: 256 MB

You are given a directed graph g, and you must determine the number of distinct cycles in g that have length less than k. Since this number can be really big, return the answer modulo m. A cycle is a non-empty sequence of nodes (not necessarily distinct) in which there is an edge from each node to the next node, and an edge from the last node in the sequence to the first node. Two cycles are distinct if their sequences are not identical. See example 0 for further clarification.

g will be given as a String[] where the jth character of the ith element indicates whether there is an edge from node i to node j (‘Y’ means there is one, and ‘N’ means there is not).

-g will have between 1 and 35 elements, inclusive.

-Each element of g will have exactly N characters, where N is the number of elements in g.

-Each character of each element of g will be ‘Y’ or ‘N’.

-The ith character of the ith element of g will be ‘N’.

-k will be between 1 and 1000000 (106), inclusive.

-m will be between 1 and 1000000000 (109), inclusive.

输入格式

First line is n ,stand for the number of the elements in graph g,then n*n matrix where the jth character of the ith element indicates whether there is an edge from node i to node j (‘Y’ means there is one, and ‘N’ means there is not).And then two number k,m discrible above.

输出格式

the number of distinct cycles in g that have length less than k.Since this number can be really big, return the answer modulo m.

样例

Input
4
NYNY
NNYN
YNNN
YNNN
6 100
7
NYNNNNN
NNYNNNN
NNNYNNN
NNNNYNN
NNNNNYN
NNNNNNY
YNNNNNN
40 13
Output
12
9
The possible cycles with length less than 6 are:
(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)
Note that (0,3), (3,0) and (0,3,0,3) are all considered different.

2 人解决,7 人已尝试。

4 份提交通过,共有 17 份提交。

9.4 EMB 奖励。

创建: 11 年,11 月前.

修改: 2 年,6 月前.

最后提交: 9 年前.

来源: TC

题目标签