自动搬运

查看原文

来自洛谷，原作者为

	N_z_ 曰：”泯然众人矣。“

搬运于2025-08-24 23:11:28，当前版本为作者最后更新于2025-03-18 19:28:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单题。

注意到我们可以获知哪些位置正确，这意味着对于每一位我们可以视作独立游戏，而完成游戏的时间是最后一个被完成的位。

考虑每一位的策略，由于是随机生成，我们询问的应当是一个排列，并且不妨将排列视为 $1,2,\cdots,n$。

$\le i$ 次可以完成的排列数量是 $i^n$，因此答案是 $\sum_{i=0}^k\frac{k^n-i^n}{k^n}$，插值求一个自然数幂和即可。