UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3250. Light Switches

Statistics 下载数据

Description

题目简述:给定一有向图,边长均为1,求总长小于k的环的个数mod m,
什么样的环属于不同详见样例。保证无自环(即g[i,i]='N')
题目详述:minecraft中有很多可爱的生物,比如creeper(更知名的名字:JJ怪)和各路僵尸。在你没有做好足够
的准备之前,遇见它们的时候只能逃跑,而且你不希望某些怪物在你辛苦建造的房子旁爆炸。所以你决定对附近的
地形进行考察,并设计好一些迂回线路,以同时应对多个怪物。

Input

第一行n表示节点个数
接下来n行长度为n的字符串,g[i,j]='Y'表示i到j有一条边,g[i,j]='N'反之。
最后一行两个整数k,m。
n<=100, k<=10^6, m<=10^9

Output

一个整数表示答案

Sample Input

4
NYNY
NNYN
YNNN
YNNN
6 100

Sample Output

12
//【样例解释】
12个解分别为:(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)。

Hint

Source