#P3250. Light Switches

    ID: 2435 传统题 1000ms 512MiB 尝试: 83 已通过: 24 难度: 6 上传者: 标签>难度分类普及+/提高-线性代数与代数矩阵快速幂等比数列求和CF1900

Light Switches

Light Switches

题目描述

在 Minecraft 中,为了躲避怪物,你需要考察附近的地形并设计迂回路线。把地形表示为一个有向图,每条边长为 11,且没有自环。

求长度为正且小于 kk 的闭合游走的数量,对 mm 取模。一次长度为 ℓ\ell 的闭合游走记为 (v0,v1,…,vℓ−1)(v_0,v_1,\ldots,v_{\ell-1})。每一对相邻顶点之间必须有对应的有向边,最后还必须有一条从 vℓ−1v_{\ell-1} 到 v0v_0 的有向边。允许重复经过顶点或边。只要有一个位置的顶点编号不同,两次游走就不同。

输入格式

第一行是顶点数 nn。顶点从 00 到 n−1n-1 编号。

接下来 nn 行,每行是一个长度为 nn 的字符串,由 Y 和 N 组成。第 ii 行、第 jj 列(从 00 开始)为 Y 时,表示存在从 ii 到 jj 的边。对角线上的字符均为 N。

最后一行包含两个正整数 k,mk,m。

输出格式

输出一个整数,表示所求数量模 mm 的余数。

样例

4
NYNY
NNYN
YNNN
YNNN
6 100
12

样例中,长度为 22 的游走是 (0,3)(0,3)、(3,0)(3,0)。长度为 33 的是 (0,1,2)(0,1,2)、(1,2,0)(1,2,0)、(2,0,1)(2,0,1)。长度为 44 的是 (0,3,0,3)(0,3,0,3)、(3,0,3,0)(3,0,3,0)。长度为 55 的是 (0,1,2,0,3)(0,1,2,0,3)、(0,3,0,1,2)(0,3,0,1,2)、(1,2,0,3,0)(1,2,0,3,0)、(2,0,3,0,1)(2,0,3,0,1)、(3,0,1,2,0)(3,0,1,2,0)。

数据规模与约定

  • 对于 30%30\% 的数据,n≤40n\le40,k≤1000k\le1000。
  • 对于 60%60\% 的数据,n≤80n\le80。
  • 对于所有数据,n≤100n\le100,k≤106k\le10^{6},m≤109m\le10^{9}。

BZOJ 归档题面