问题1493--八维

1493: 八维

时间限制: 15 Sec  内存限制: 256 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]
题目描述

我们将一个M行N列的字符矩阵无限复制,可以得到一个无限字符矩阵。 例如,对于以下矩阵

honi

hsin

可以无限复制出矩阵

...honihonihonihoni...

...hsinhsinhsinhsin...

...honihonihonihoni...

...hsinhsinhsinhsin...

我们认为矩阵是八连通的。八连通,指矩阵中的每个位罝与上下左右和四个 斜向(左上、右上、左下、右下)的位罝相邻。因此,从矩阵任意位罝出发沿八 个方向中的任意一个都可以无限延长。

如果我们随机选择一个位罝和一个方向,则可以从此位罝开始沿此方向连续选取K个字符组成一个宇符串。问,两次这样操作得到两个相同字符串的概率是多少。(假设随机选择时任意位罝是等可能的,任意方向也是等可能的) 

例如,输入

122

ab

则输出

5/16



输入

第一行是三个整数M,N,K。

接下来M行,每行一个由小写英文字母组成的长度为N的字符串,即 的字符矩阵。保证矩阵中至少出现两种不同字符。

输出

输出一行,为一个化简后的分数,表示概率。

样例输入 Copy
3 3 10
ban
ana
nab
样例输出 Copy
2/27
提示
【样例解释】 
样例一中,一次操作共有 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。
来源/分类