AT_joi2006yo_e.JOI 2006 予選 問題5

设想一个游戏场景：有 $k$ 组卡片，每组有 $n$ 张卡片，分别标有从 $1$ 到 $n$ 的数字。在开始游戏前，我们会将这 $kn$ 张卡片进行充分洗牌，然后将它们分成 $n$ 堆，每堆 $k$ 张卡片，并从左至右依次排列。我们称第 $i$ 堆卡片为「山 $i$」。

游戏以山 $1$ 开始，每次从当前山顶抽取一张卡片（抽取后不放回原处）。如果抽出的卡片上标有数字 $i$，那么下一步则转至山 $i$，继续抽取此山顶的一张卡片。这个过程持续进行，直到所有的山都被抽空，就宣告成功。而如果在某一时刻应该抽取的山已无卡片可抽时，就意味着失败。

如果游戏中途失败，你可以选择直接结束游戏，或是保留剩下的卡片以当前的装态重新开始并尝试继续游戏。重新开始时，从最左边仍有卡片的山顶开始抽取，规则与之前相同。游戏过程最多允许重新开始 $m$ 次，其中 $m$ 可以是 $0$ 或 $1$。也就是说，你可以不重新开始或只重新开始一次。不同的初始卡片排列会影响游戏结果，可能不重新开始就成功，也可能需要重新开始才成功，当然也可能在重新开始后依旧失败。由于洗牌充分，每种初始排列出现的概率相同。我们的目标是在最多 $m$ 次重新开始内成功完成游戏的概率 $p$，要求输出 $p$ 的小数表示，保留小数点后 $r$ 位。

输出时应注意，如果有一个整数 $K$ 使得 $p \times 10^K$ 为整数，则小数部分即使全为零也请完整输出。例如，若 $p = 3/8 = 0.375$，当 $r = 5$ 时，输出 0.37500；当 $r = 2$ 时，输出 0.37。对于 $p = 1.0$ 的情况，若 $r = 3$，则输出 1.000。虽然 $0.150000\cdots$ 可以表示为循环小数 $0.1499999\cdots$，但在这种情况下请采用前者的表示形式。

输入包含一行，四个整数 $n, k, m, r$，分别表示卡片种类数、每种卡片的数量、最多重新开始的次数和输出的小数位数。

输出在 $m$ 次以内成功完成游戏的概率 $p$，以小数形式表示并保留小数点后 $r$ 位。

$1 \leq n \leq 10\,000$，$1 \leq k \leqq 100$，$m = 0$ 或 $m = 1$，$1 \leq r \leq 10\,000$。

本翻译由 AI 自动生成