题解

思路

令 dp[i] 表示当前轮中，从编号同余于 $i$ 的选手开始、连续 $2^r$ 人进行比赛后的胜者手势。

做法

初始 $r=0$ 时 dp[i]=S[i]。把规模从 $2^r$ 翻倍到 $2^{r+1}$ 时，左半胜者是 dp[i]，右半从 $i+2^r$ 开始；由于选手手势以 $N$ 为周期，只需访问 dp[(i+2^r) mod N]，两者按剪刀石头布规则决出新状态。

每轮把偏移量 $2^r\bmod N$ 翻倍并对 $N$ 取模，连续更新 $K$ 轮，最后 dp[0] 就是完整比赛的胜者。

复杂度

时间复杂度为 $O(NK)$，空间复杂度为 $O(N)$。