自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:01:13，当前版本为作者最后更新于2020-08-23 11:07:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

其他题解都是生成函数做的，这里给个更加直观的方法（事实上可以严格化，不过需要更高层次的数学知识）。

这个方法是从这篇知乎回答里看来的。

假设已经只保留了一个牛人酋长，其名字为 $A=a_1a_2\cdots a_l$。

假设王国旁边开了一座赌场，每单位时间（就称为“秒”吧）会有一个赌徒带着 $1$ 铜币进入赌场。

赌场规则很简单：可以支付 $x$ 铜币赌下一秒会唱出 $y$，如果猜对了就返还 $nx$ 铜币，否则不返还。显然，这是一个公平赌博。

每个赌徒会如下行动：支付 $1$ 铜币赌下一秒会唱出 $a_1$，如果赌对了就支付得到的 $n$ 铜币赌下一秒会唱出 $a_2$，如果还对了就支付得到的 $n^2$ 铜币赌下一秒会唱出 $a_3$，等等，以此类推，最后支付 $n^{l-1}$ 铜币赌下一秒会唱出 $a_l$。

一旦连续唱出了 $a_1a_2\cdots a_l$，赌场老板就会认为自己亏大了而关门，并驱散所有赌徒。

那么关门前发生了什么呢？以 $A=\{1,4,1,5,1,1,4,1\},n=5$ 为例：

• 最后一位赌徒拿着 $5^1$ 铜币离开；
• 倒数第三位赌徒拿着 $5^3$ 铜币离开；
• 倒数第八位赌徒拿着 $5^8$ 铜币离开；
• 其他所有赌徒空手而归。

$1,3$ 实际上就是原序列的所有 border 的长度。

这时候最神奇的一步来了：由于这个赌博游戏是公平的，因此赌场应该期望下不赚不赔，因此关门时期望来了 $5+5^3+5^8$ 个赌徒，因此期望需要 $5+5^3+5^8$ 单位时间唱出这个名字。

同理，即可知道对于一般的 $A$，答案为：

直接跑一遍 KMP 求出 border 就好了。代码很短也很好写，略了。