Light Switches
题目描述
在 Minecraft 中,为了躲避怪物,你需要考察附近的地形并设计迂回路线。把地形表示为一个有向图,每条边长为 1,且没有自环。
求长度为正且小于 k 的闭合游走的数量,对 m 取模。一次长度为 ℓ 的闭合游走记为 (v0,v1,…,vℓ−1)。每一对相邻顶点之间必须有对应的有向边,最后还必须有一条从 vℓ−1 到 v0 的有向边。允许重复经过顶点或边。只要有一个位置的顶点编号不同,两次游走就不同。
输入格式
第一行是顶点数 n。顶点从 0 到 n−1 编号。
接下来 n 行,每行是一个长度为 n 的字符串,由 Y 和 N 组成。第 i 行、第 j 列(从 0 开始)为 Y 时,表示存在从 i 到 j 的边。对角线上的字符均为 N。
最后一行包含两个正整数 k,m。
输出格式
输出一个整数,表示所求数量模 m 的余数。
样例
4
NYNY
NNYN
YNNN
YNNN
6 100
12
样例中,长度为 2 的游走是 (0,3)、(3,0)。长度为 3 的是 (0,1,2)、(1,2,0)、(2,0,1)。长度为 4 的是 (0,3,0,3)、(3,0,3,0)。长度为 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)。
数据规模与约定
- 对于 30% 的数据,n≤40,k≤1000。
- 对于 60% 的数据,n≤80。
- 对于所有数据,n≤100,k≤106,m≤109。
BZOJ 归档题面