前置知識

這題的核心推導下面會從頭講；要先讀的是兩件「為什麼直接模擬會太慢」的背景：

• vector 的 erase 很貴：語法書 10.5——移除一個元素，後面整段都要搬，一次 \(O(n)\)。
• 約瑟夫問題：語法書 16.5——本題是它的一般版（每隔一位改成每數到第 \(M\) 位、而且只淘汰 \(K\) 人）；那一節示範了「逐一 erase」在 \(n = 2 \times 10^5\) 時為什麼 TLE。
• 複雜度估算：NTUCPC Guide〈複雜度〉。

簡潔題意

\(N\) 個人圍成一圈，編號 \(1 \sim N\)。炸彈從 \(1\) 號開始傳，拿到的人算第 \(1\) 個，傳到第 \(M\) 個人時爆炸、這個人淘汰出圈，炸彈再從他的下一位開始重數。炸彈只會爆 \(K\) 次（\(1 \le K < N\)），第 \(K\) 個被淘汰的人的下一位（還在圈裡的）就是幸運者，輸出他的編號（\(N \le 2 \times 10^5\)、\(M \le 10^6\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(20\) 分）：\(N \le 100\)，\(M \le 10\)，\(K = N - 1\)。
• 子題組 2（\(30\) 分）：\(N \le 10000\)，\(M \le 10^6\)，\(K = N - 1\)。
• 子題組 3（\(20\) 分）：\(N \le 2 \times 10^5\)，\(M \le 10^6\)，\(K = N - 1\)。
• 子題組 4（\(30\) 分）：無額外限制。

先拿下 50 分：用 vector 照規則模擬

把還在圈裡的人依序放進一個 vector，記住「下一個拿到炸彈的人」在 vector 裡的索引 cur。拿到炸彈的人算第 \(1\) 個，所以第 \(M\) 個人在 cur + M - 1；圈是圓的，超過尾巴要繞回開頭——取餘數 % alive.size() 一次處理掉，\(M\) 比人數還大、繞好幾圈也一樣。erase 掉他之後，後面的人整段往前補，原本在他下一位的人剛好就坐進了索引 cur，不用另外調整；只有他是最後一個元素時 cur 會等於新的人數，再取一次餘數繞回 \(0\)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> alive;
    for (int i = 1; i <= n; i++) alive.push_back(i);

    int cur = 0;                                   // 下一個拿到炸彈的人（索引）
    for (int t = 0; t < k; t++) {
        cur = (cur + m - 1) % alive.size();        // 從 cur 數起的第 m 個人
        alive.erase(alive.begin() + cur);          // 淘汰；他的下一位補進索引 cur
        cur %= alive.size();                       // 淘汰的是最後一個 → 繞回開頭
    }
    cout << alive[cur] << '\n';
    return 0;
}

跑完 \(K\) 次，alive[cur] 就是第 \(K\) 個淘汰者的下一位。每次 erase 最多搬 \(N\) 個人，\(K\) 次就是 \(O(NK)\)：子題組 2 的 \(N = 10^4\) 約 \(10^8\) 次搬動，不到 \(0.01\) 秒；\(N = 2 \times 10^5\) 時 \(M = 1\) 的測資要搬 \(2 \times 10^{10}\) 次，本站實測約 \(1.4\) 秒，超過時限——子題組 1、2 的 \(50\) 分穩穩到手，子題組 3、4 要換個做法。

從 50 分到 100 分：把淘汰倒著想

模擬慢在「每淘汰一個人就要搬一次」。先看一件事：炸掉一個人之後，剩下的人還是在玩同一個遊戲——只是少了一個人、起點換成淘汰者的下一位（圖 1）。

既然每一圈都是同一個遊戲，就換個角度：不去追蹤誰被淘汰，直接追蹤幸運者在每一圈裡的位置。

先定一個講法：某個時刻圈裡剩 \(s\) 個人、炸彈正要從某人開始數——把這個人叫做這一圈的起點，幸運者在這一圈裡是「從起點數起的第 \(g(s)\) 個」（起點本人是第 \(0\) 個）。

• 剩 \(N - K\) 人的時候，炸彈已經爆完 \(K\) 次，不會再爆。幸運者是最後一位淘汰者的下一位，也就是這一圈的起點本人：\(g(N - K) = 0\)。

• 剩 \(s\) 人的時候（\(s > N - K\)），這一圈還會爆一次。從起點數起，被炸的是第 \((M - 1) \bmod s\) 個；新的一圈（\(s - 1\) 人）從他的下一位開始數，那個人在這一圈是第 \(M \bmod s\) 個。新圈的幸運者是從新起點數起的第 \(g(s - 1)\) 個，換算回這一圈，就是從舊起點數起的第 \(M + g(s - 1)\) 個——繞圈要取餘數：

  \[g(s) = \bigl(g(s - 1) + M\bigr) \bmod s\]

  圖 2 用範例 1 的第一次爆炸對照：新圈（\(4\) 人）的第 \(0, 1, 2, 3\) 個，就是舊圈（\(5\) 人）的第 \(2, 3, 4, 5\) 個，而第 \(5\) 個超過人數、繞回第 \(0\) 個。

從 \(g(N - K) = 0\) 出發，\(s\) 從 \(N - K + 1\) 一路算到 \(N\)：最後 \(g(N)\) 是「從 \(1\) 號數起的第幾個」，編號就是 \(g(N) + 1\)。用範例 1（\(N = 5\)、\(M = 2\)、\(K = 4\)）走一遍（圖 3）：\(N - K = 1\)，\(g(1) = 0\)；\(g(2) = (0 + 2) \bmod 2 = 0\)；\(g(3) = (0 + 2) \bmod 3 = 2\)；\(g(4) = (2 + 2) \bmod 4 = 0\)；\(g(5) = (0 + 2) \bmod 5 = 2\)，答案 \(2 + 1 = 3\)。圖 3 每一圈都把真正留在圈裡的人畫出來，可以逐圈對：\(3\) 號在每一圈裡的位置，正好就是算出來的 \(g\)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    int g = 0;                                 // 剩 n-k 人時，幸運者就是起點本人
    for (int s = n - k + 1; s <= n; s++)       // 圈子從 n-k+1 人一路長回 n 人
        g = (g + m) % s;
    cout << g + 1 << '\n';
    return 0;
}

只有 \(K\) 次加法和取餘數，\(O(K)\)；g + m 最大約 \(2 \times 10^5 + 10^6\)，int 綽綽有餘。\(K = N - 1\) 時 \(N - K = 1\)，就是從一個人的圈開始算——這正是經典的「最後一人」約瑟夫問題，所以子題組 1 到 3 和子題組 4 用的是同一份程式。

測過再交：範例的 \(K\) 都貼著 \(N\)

範例 1 是 \(K = N - 1\)、範例 2 是 \(K = N - 2\)，都是「爆到快沒人」。沒蓋到的：只爆一次、\(M = 1\)（照順序淘汰）、\(M\) 比人數還大、最小的 \(N = 2\)、答案剛好是 \(N\) 號。

五筆都親眼看過正確，這題就穩了。