#P11813. [PA 2015] 机器人 / Roboty

[PA 2015] 机器人 / Roboty

题目背景

译自 Potyczki Algorytmiczne 2015 R5 Roboty [A] (ROB)。1s,256M\texttt{1s,256M}

题目描述

nn 个区域,编号 1n1\sim n。编号 1b1\sim b 的区域是基地

给定 nn 个非空集合 A1,A2,,AnA_1,A_2,\cdots,A_n

rr 个机器人在区域里。第 ii 个机器人的初始位置为 sis_i

你可以下达任意次移动指令。每次指令下达后,设第 ii 个机器人的位置为 xix_i,则第 ii 个机器人会等概率独立随机地移动到 AxiA_{x_i} 中的任意一个地点。

是否存在一个非负整数 kk,使得下达 kk 次指令后,每个机器人都一定回到基地(即位于编号 1b1\sim b 的基地中)?找到满足条件的任意一个 kk

保证如果存在 kk,则 kk 的最小值严格小于 1020010^{200}

输入格式

第一行三个正整数 n,b,rn,b,r

接下来 nn 行,第 ii 行一个长度为 nn01\texttt{01}ai,ja_{i,j}ai,j=1    jAia_{i,j}=1 \iff j\in A_i

(n+2)(n+2) 行,rr 个递增的正整数 s1,,srs_1,\ldots,s_r

输出格式

如果存在这样的 kk,输出一行一个非负整数 kk;否则输出一行一个 -1\texttt{-1}

评测时将忽略多余的前导零。你应当保证你输出的 kk 不大于 101000010^{10000},否则可能导致 UKE。

保证如果存在 kk,则 kk 的最小值严格小于 1020010^{200}

4 2 2
0100
0010
1001
1000
3 4
2
4 2 2
0100
0010
1001
1000
2 3
-1

提示

  • 2n2002\le n\le 200
  • 1b,rn1\le b,r\le n
  • 1s1<s2<<srn1\le s_1\lt s_2\lt \ldots \lt s_r \le n

保证如果存在 kk,则 kk 的最小值严格小于 1020010^{200}