P4472 [BJWC2018] 八维

我们将一个 $M$ 行 $N$ 列的字符矩阵无限复制，可以得到一个无限字符矩阵。例如，对于以下矩阵: $$\begin{aligned} & \verb!honi! \\ & \verb!hsin! \\ \end{aligned}$$ 可以无限复制出矩阵 $$\begin{aligned} & \verb!...honihonihonihoni...! \\ & \verb!...hsinhsinhsinhsin...! \\ & \verb!...honihonihonihoni...! \\ & \verb!...hsinhsinhsinhsin...! \\ \end{aligned}$$ 我们认为矩阵是八连通的。八连通， 指矩阵中的每个位置与上下左右和四个斜向（左上、右上、左下、右下）的位置相邻。因此，从矩阵任意位置出发沿八个方向中的任意一个都可以无限延长。 如果我们随机选择一个位置和一个方向，则可以从此位置开始沿此方向连续选取 $K$ 个字符组成一个字符串。问，两次这样操作得到两个相同字符串的概率是多少。(假设随机选择时任意位置是等可能的，任意方向也是等可能的)

无

无

**【样例解释】** 样例一中，一次操作共有 $16$ 种可能，其中得到 $\verb!aa!$ 的概率是 $1/8$，得到 $\verb!ab!$ 的概率是 $3/8$,得到bb 的概率是 $1/8$，得到 $\verb!ba!$ 的概率是 $\verb!3/8!$。两次操作结果相同的 概率是 $5/16$。 **【数据规模和约定】** - 对于 $30\%$ 的测试数据：$M, N ≤ 10$，$K ≤ 100$。 - 对于 $50\%$ 的测试数据：$M = N$。 - 对于 $100\%$ 的测试数据 ：$1 ≤ M,N ≤ 500$，$2 ≤ K ≤ 10^9$。