4792: [BJWC2018] 八维
Memory Limit:256 MB
Time Limit:15.000 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:1
Description
我们将一个 行 列的字符矩阵无限复制,可以得到一个无限字符矩阵。例如,对于以下矩阵:
可以无限复制出矩阵
我们认为矩阵是八连通的。八连通, 指矩阵中的每个位置与上下左右和四个斜向(左上、右上、左下、右下)的位置相邻。因此,从矩阵任意位置出发沿八个方向中的任意一个都可以无限延长。
如果我们随机选择一个位置和一个方向,则可以从此位置开始沿此方向连续选取 个字符组成一个字符串。问,两次这样操作得到两个相同字符串的概率是多少。(假设随机选择时任意位置是等可能的,任意方向也是等可能的)
Input
第一行是三个整数 。
接下来 行, 每行一个由小写英文字母组成的长度为 的字符串,即 的字符矩阵。保证矩阵中至少出现两种不同字符。
Output
输出一行,为一个化简后的分数,表示概率。
Sample Input Copy
3 3 10
ban
ana
nab
Sample Output Copy
2/27
HINT
【样例解释】
样例一中,一次操作共有 16 种可能,其中得到 aa 的概率是 1/8,得到 ab 的 概率是 3/8,得到 bb 的概率是 1/8,得到 ba 的概率是 3/8。两次操作结果相同的 概率是 5/16。
【数据规模和约定】
30%的测试数据:M, N ≤ 10,K ≤ 100。
50%的测试数据:M = N。
100%的测试数据:1 ≤ M, N ≤ 500,2 ≤ K ≤ 109。