文件读写

• 输入文件random.in
• 输出文件random.out

限制

• 2000ms
• 512MB

题目描述

徐老师最近在疯狂的出题，这天他准备了一道字符串相关的题目

需要随机生成一些字符串

他生成字符串的方法是这样的：

1. 准备一个 $n * m$ 的字符矩阵 $A$（仅包含小写字母）
2. 随机选取矩阵中的一个位置 $x,y$ 作为起点，然后从上(x-1,y)、下(x+1,y)、左(x,y-1)、右(x,y+1)、左上(x-1,y-1)、右上(x-1,y+1)、左下(x+1,y-1)、右下(x+1,y+1) 中随机一个方向，再结合徐老师需要生成的长度 $len$，作为一个四元组 $(x,y,dir,len)$
3. 以 $A[x][y]$ 为起点，以 $dir$ 为方向，移动 $len$ 次，获得一个长度为 $len$ 的字符串
4. 特别的，如果超出了矩阵范围，你可以认为这个矩阵是一个 无限矩阵，即将这个矩阵在周围无限复制粘贴扩展出空间

例如如下矩阵

n = 3, m = 4
abcd
efgh
ijkl
无限扩展后变成
......................
......................
......................
...abcdabcdabcdabcd...
...efghefghefghefgh...
...ijklijklijklijkl...
...abcdabcdabcdabcd...
...efghefghefghefgh...
...ijklijklijklijkl...
......................
......................
......................

四元组 $(2,2,上,10)$ 生成的字符串为 $fbjfbjfbjf$

四元组 $(2,2,右上,10)$ 生成的字符串为 $fclebkhajg$

四元组 $(3,2,左上,10)$ 生成的字符串为 $jedkfalgbi$

现在徐老师想知道，如果他运行两次这个程序，生成相同字符串的概率是多少？

输入格式

输入第一行包含三个整数 $n,m,len$ 表示矩阵大小

接下来 $n$ 行包含 $m$ 个小写字母，表示矩阵

输出格式

输出一行表示结果，答案以最简分数(p/q)的形式表示，保证答案中 $q$ 不为 $1$

数据范围

测试数据编号	$n,m$	$k$	特殊性质
$1 \sim 2$	$1 \leq n,m \leq 20$	$1 \leq len \leq 20$	无
$3 \sim 4$	$1 \leq n,m \leq 50$	$1 \leq len \leq 50$
$5 \sim 7$	$1 \leq n,m \leq 100$	$1 \leq len \leq 10^9$	$n=m$
$8 \sim 10$	$1 \leq n,m \leq 200$		无

样例输入1

1 2 1
ab

样例输出1

1/2

样例解释1

四元组 $(1,1,任意方向,1)$ 生成的字符串都是 $a$ 四元组 $(1,2,任意方向,1)$ 生成的字符串都是 $b$ 生成的字符串一共有 $16$ 种情况，其中 $8$ 种为 $a$，$8$ 种为 $b$ 那么生成相同字符串的概率即为 $1/2$

样例输入2

1 2 2
ab

样例输出2

5/16

样例输入3

2 4 3 
abce 
adec

样例输出3

19/512

样例输入4

3 4 10 
aooa
boob
aooa

样例输出4

29/576