题解 P4548 【[CTSC2006]歌唱王国】
WYXkk
·
·
题解
其他题解都是生成函数做的，这里给个更加直观的方法（事实上可以严格化，不过需要更高层次的数学知识）。
这个方法是从这篇知乎回答里看来的。
假设已经只保留了一个牛人酋长，其名字为 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 铜币离开；
- 其他所有赌徒空手而归。
这时候最神奇的一步来了：由于这个赌博游戏是公平的，因此赌场应该期望下不赚不赔，因此关门时期望来了 $5+5^3+5^8$ 个赌徒，因此期望需要 $5+5^3+5^8$ 单位时间唱出这个名字。
同理，即可知道对于一般的 $A$，答案为：
$$\sum\limits_{a_{[1,c]}=a_{[n-c+1,n]}} n^c$$
直接跑一遍 KMP 求出 border 就好了。代码很短也很好写，略了。