CVBB ACM Team

--- 2020-2021:teams:alchemist:mountvoom:training1 [2020/05/13 20:19]
mountvoom [H. 时空栈]
+++ 2020-2021:teams:alchemist:mountvoom:training1 [2020/05/13 20:25] (当前版本)
mountvoom [I. 纸牌]
@@ 行 105: / 行 105: @@
 ===== I. 纸牌 =====
+**题意:**
+桌上有一叠共$n$张牌，从顶向下标号为$1\sim n$。
+这一叠牌做$k, k \leq 10^{18}$次操作，其中第$i$次操作会将牌堆顶的牌放在牌堆中的某个位置，从而满足这张牌成为自顶向下第$(i - 1) % (n - 1) + 2$张牌。求$k$次操作以后这叠牌自顶向下的编号情况。
+**题解:**
+假设$k \leq (n - 1)$，那么我们可以这样模拟：
+观察到如果此时顶部纸牌插入到了$x$这张牌的后面，那么下次要插入的纸牌位置就是nxt[nxt[x]]，用链表模拟即可。
+当$k$很大时，假设$n - 1$操作后第$i$张牌编号为$p[i]$，那么$2(n - 1)$次操作后，第$i$张牌编号为$p[p[i]]$，这一部分可以倍增或者把排列$p$拆成循环来处理。
+剩下的$k \% (n - 1)$次直接模拟即可。
 ===== J. 斐波那契和 =====