刻的完整推導(dǎo))
早上在評(píng)測(cè)系統(tǒng)里刷到這道題的時(shí)候我第一反應(yīng)是“B - Two chandeliers”這個(gè)名字挺唬人點(diǎn)進(jìn)去一看兩盞吊燈每盞按各自的周期循環(huán)變色問第 k 次“不和諧”的時(shí)刻是什么時(shí)候。這種題目看名字像是模擬題但稍微掃一眼數(shù)據(jù)范圍就知道暴力掃時(shí)間軸一定 T 到姥姥家。真正把這道題做出來之后我發(fā)現(xiàn)它其實(shí)是一道很典型的“周期性事件統(tǒng)計(jì)”題核心工具就是擴(kuò)展中國剩余定理EXCRT和二分答案兩者配合得嚴(yán)絲合縫。這篇博客我就把整個(gè)推導(dǎo)過程、實(shí)現(xiàn)細(xì)節(jié)、以及我實(shí)際踩過的坑都寫下來希望能給正在刷這類題的同學(xué)一點(diǎn)參考。1. 題目拆解兩盞吊燈的周期問題到底在算什么1.1 先把題意翻譯成數(shù)學(xué)語言題目里兩盞吊燈第一盞有 n 個(gè)位置第二盞有 m 個(gè)位置每個(gè)位置都有一個(gè)顏色值。從某個(gè)時(shí)刻開始第一盞燈每個(gè)單位時(shí)間會(huì)切換到下一個(gè)位置第 t 個(gè)時(shí)刻它顯示的顏色就是數(shù)組 a 的第t mod n個(gè)位置第二盞燈同理顯示的是數(shù)組 b 的第t mod m個(gè)位置。如果某一時(shí)刻兩盞燈顯示的顏色相同那就認(rèn)為這一秒是“和諧”的否則就是不和諧?，F(xiàn)在給一個(gè)很大的數(shù) k問第 k 個(gè)不和諧的時(shí)刻具體是哪個(gè)時(shí)刻。這句話翻譯過來其實(shí)就是給了兩個(gè)周期分別為 n 和 m 的序列我們要找時(shí)間軸上的事件分布。如果你手上拿的是兩個(gè)長度幾百萬的數(shù)組直接 for 循環(huán)從 t 0 一直往上遞增數(shù)到第 k 個(gè)不和諧的時(shí)刻邏輯上沒錯(cuò)但 k 的范圍可能到 1e18你數(shù)到頭發(fā)白了都數(shù)不完。所以關(guān)鍵是把“周期”利用起來而不是把時(shí)間軸一條一條地梭哈。我個(gè)人的習(xí)慣是先把所有變量統(tǒng)一成“時(shí)刻 t 從 0 開始”的模型。很多題目里會(huì)用第 1 秒、第 2 秒這種 1 基描述但做數(shù)論題的時(shí)候 0 基會(huì)讓取模運(yùn)算干凈很多后面代碼里的邊界也能少踩很多坑。如果你發(fā)現(xiàn)原題是 1 基的可以先在輸入的時(shí)候把數(shù)組下標(biāo)或者查詢邏輯做一次便宜轉(zhuǎn)換后面統(tǒng)一按 0 基處理。1.2 為什么暴力解法必然超時(shí)假設(shè) n 和 m 都在 2e5 這個(gè)量級(jí)k 在 1e18 量級(jí)那直接枚舉時(shí)間軸的做法肯定不行。有些人可能會(huì)說那我把 a 和 b 拉成同樣長度找到一個(gè)公共周期 L lcm(n, m)然后在一個(gè) L 內(nèi)統(tǒng)計(jì)不和諧的次數(shù)再用 k 整除一下不就行了這個(gè)思路方向是對(duì)的但里面藏著一個(gè)大坑一個(gè)公共周期 L 內(nèi)到底有多少次不和諧如果你還是用兩重循環(huán)去暴力統(tǒng)計(jì)復(fù)雜度 O(L) 的代價(jià)在 L 很大的時(shí)候照樣不可接受。這里 L 可能達(dá)到 n * m / gcd(n, m) 的量級(jí)在 n、m 都是 2e5 的時(shí)候L 能到 4e10直接內(nèi)存和時(shí)間雙爆炸。所以我們就需要更聰明的辦法不直接枚舉每個(gè)時(shí)刻而是反過來枚舉“哪些位置組合會(huì)在某一時(shí)刻同時(shí)出現(xiàn)”這個(gè)組合的數(shù)量通常遠(yuǎn)小于 L。于是題目就變成了一個(gè)數(shù)論問題給定兩個(gè)下標(biāo) i 和 j是否存在某個(gè)時(shí)刻 t使得第一盞燈正好走到位置 i第二盞燈正好走到位置 j這就是一個(gè)同余方程組的問題也就是我們接下來要說的擴(kuò)展中國剩余定理的用武之地。2. 匹配時(shí)刻的同余方程模型這是 EXCRT 的核心切入2.1 位置對(duì)齊的本質(zhì)是解同余方程組先看一個(gè)具體問題。如果第一盞燈的長度 n 4第二盞燈的長度 m 6。現(xiàn)在我想知道是否存在某個(gè)時(shí)刻 t使得第一盞燈正好在第 1 個(gè)位置下標(biāo) 1第二盞燈正好在第 5 個(gè)位置下標(biāo) 5。這個(gè)條件寫出來就是t ≡ 1 (mod 4) t ≡ 5 (mod 6)如果存在這樣的 t那這個(gè)時(shí)刻就是兩個(gè)指定位置“對(duì)上”的時(shí)刻。由于兩個(gè)數(shù)組都是周期性的一旦有一組解 t0那么所有解就是t0 k * lcm(4, 6)也就是說這對(duì)位置組合每隔 12 個(gè)時(shí)刻就會(huì)重新對(duì)齊一次。這里要特別提醒不要下意識(shí)認(rèn)為“只要 a[i] b[j] 就能在某一個(gè)時(shí)刻對(duì)上”。位置對(duì)齊這件事跟顏色是否相同其實(shí)沒有直接關(guān)系。真正決定能否對(duì)齊的是兩個(gè)下標(biāo)之間的相位關(guān)系。比如 n 4m 6i 1j 2你會(huì)發(fā)現(xiàn) t 永遠(yuǎn)不可能既等于 1 mod 4 又等于 2 mod 6因?yàn)檫@兩個(gè)條件本身就是沖突的。所以對(duì)于任何一對(duì)位置 (i, j)我們首先要判斷同余方程組有沒有解有解的話這個(gè)解落在哪個(gè)時(shí)刻然后才談得上“這個(gè)時(shí)刻顏色匹不匹配”。2.2 普通 CRT 不夠用EXCRT 的合并公式推導(dǎo)很多同學(xué)第一反應(yīng)是中國剩余定理CRT。但 CRT 有一個(gè)強(qiáng)前提模數(shù)之間兩兩互質(zhì)。這里的 n 和 m 顯然不一定互質(zhì)4 和 6 就不互質(zhì)所以我們必須用擴(kuò)展中國剩余定理EXCRT它不需要模數(shù)互質(zhì)核心是對(duì)兩個(gè)同余方程進(jìn)行合并。假設(shè)現(xiàn)在有兩個(gè)方程x ≡ r1 (mod m1) x ≡ r2 (mod m2)把第一個(gè)方程寫成x r1 m1 * t的形式代入第二個(gè)方程得到r1 m1 * t ≡ r2 (mod m2) m1 * t ≡ r2 - r1 (mod m2)接下來這個(gè)形式化成線性不定方程m1 * t m2 * y r2 - r1設(shè) d gcd(m1, m2)。如果(r2 - r1) % d ! 0整個(gè)方程組必然無解。如果有解先用擴(kuò)展歐幾里得算法求出m1 * t m2 * y d的一組特解然后把右邊從 d 放大到(r2 - r1)/d倍就能得到 t 的一個(gè)特解 t0。最后把所有解合并成新的同余方程x ≡ r1 m1 * t0 (mod lcm(m1, m2))這樣兩個(gè)方程就變成了一個(gè)方程。后面再加進(jìn)來新的方程就繼續(xù)用同樣的方式合并直到所有方程處理完。這也是“擴(kuò)展中國剩余定理”最常見的兩兩合并套路。我覺得用一個(gè)生活化的類比比較好理解兩盞吊燈像兩個(gè)不同齒數(shù)的齒輪在轉(zhuǎn)你想知道某個(gè)齒和某個(gè)齒會(huì)不會(huì)在某一次同時(shí)咬合。EXCRT 就是專門計(jì)算這兩個(gè)齒輪咬合周期的工具它不看齒的顏色只看齒的位置是否能被同一個(gè)時(shí)刻“同時(shí)觸發(fā)”。2.3 一個(gè)小優(yōu)化先用 gcd 快速過濾無解組合實(shí)際編碼的時(shí)候如果我們對(duì)每一對(duì)顏色相同的位置都去跑一次 EXCRT雖然復(fù)雜度也不高但總歸有點(diǎn)浪費(fèi)。有個(gè)非常簡單的預(yù)判條件對(duì)于方程x ≡ i (mod n) x ≡ j (mod m)設(shè) g gcd(n, m)方程有解的必要且充分條件是i % g j % g。這個(gè)結(jié)論來自線性同余方程的基本性質(zhì)本質(zhì)上是說兩個(gè)下標(biāo)必須落在同一個(gè)“模 g 的同余類”里。比如 n 4m 6g 2那么 i 為奇數(shù)時(shí) j 也必須是奇數(shù)i 為偶數(shù)時(shí) j 也必須是偶數(shù)否則直接跳過不用再算 EXCRT。別看這個(gè)小判斷不起眼它能幫我們過濾掉大量無效位置對(duì)。特別是當(dāng) a 和 b 數(shù)組里重復(fù)顏色很多的時(shí)候先做一次% g的過濾能少掉好幾次 exgcd 運(yùn)算。我在自己實(shí)現(xiàn)的時(shí)候是先建了一個(gè)哈希表記錄數(shù)組 b 中每種顏色出現(xiàn)的所有位置然后遍歷數(shù)組 a 的每個(gè)位置 i去找 b 中同色的所有位置 j先檢查i % g j % g通過了再去求具體的對(duì)齊時(shí)刻。當(dāng)然如果同色位置對(duì)非常多你還可以選擇遍歷位置數(shù)量少的那一側(cè)這是一個(gè)啟發(fā)式的優(yōu)化能進(jìn)一步降低枚舉成本。3. 二分答案為什么找“第 k 次不和諧”用二分最穩(wěn)3.1 匹配事件在一個(gè)大周期內(nèi)只會(huì)出現(xiàn)一次我們繼續(xù)看整個(gè)時(shí)間軸的結(jié)構(gòu)。所有位置對(duì)的對(duì)齊時(shí)刻如果我們只關(guān)心“顏色相同”的匹配事件那么每一對(duì)滿足條件的 (i, j) 都會(huì)產(chǎn)生一個(gè)初始時(shí)刻 x0并且之后每隔 L lcm(n, m) 重復(fù)一次。這里有個(gè)很重要的結(jié)論在同一個(gè)長度 L 的周期里每個(gè)匹配事件最多出現(xiàn)一次。因?yàn)橥粋€(gè)位置對(duì)i mod n 和 j mod m 都確定在同一段周期內(nèi)只可能有一個(gè)對(duì)齊時(shí)刻不可能出現(xiàn)兩次。所以我們可以先把所有“匹配事件”對(duì)應(yīng)的初始時(shí)刻 x0 收集到一個(gè)數(shù)組里比如叫matchPos。因?yàn)槊總€(gè)事件在 L 周期內(nèi)最多出現(xiàn)一次所以matchPos里的元素個(gè)數(shù)就是每周期匹配事件的總次數(shù)。這樣一來站在一整條時(shí)間軸上匹配事件就變成了若干個(gè)以 L 為間隔的等差到達(dá)序列。接下來的問題就變成了給定任意時(shí)間 T怎么快速統(tǒng)計(jì)從 0 到 T 這段時(shí)間里總共有多少次匹配事件。3.2 如何快速統(tǒng)計(jì)任意時(shí)間之前的匹配次數(shù)假設(shè)我們已經(jīng)有了matchPos數(shù)組里面存了所有匹配事件在第一個(gè)周期內(nèi)的位置并且已經(jīng)排好序。那么對(duì)于任意時(shí)刻 T匹配事件的總次數(shù)可以這樣算先數(shù)出 T 里面包含了多少個(gè)完整的 L 周期也就是full T / L每個(gè)完整周期里有matchPos.size()個(gè)匹配事件再處理剩下不到一個(gè)周期的部分rem T % L只需要統(tǒng)計(jì)matchPos里有多少個(gè)值不超過rem這一步用upper_bound二分查找就行。把這段寫成代碼就是long long countMatch(long long T, long long L, const vectorlong long matchPos) { long long full T / L; long long rem T % L; long long cnt (long long)matchPos.size(); long long res full * cnt; res upper_bound(matchPos.begin(), matchPos.end(), rem) - matchPos.begin(); return res; }注意這里的 T 是“從時(shí)刻 0 到時(shí)刻 T”的閉區(qū)間也就是說時(shí)刻 T 本身是包含在統(tǒng)計(jì)范圍內(nèi)的。如果題目里第 1 個(gè)時(shí)刻是從 t 1 開始你需要自己換算一下。我寫題的時(shí)候很容易在這里搞混所以后來干脆全部統(tǒng)一成 0 基閉區(qū)間統(tǒng)計(jì)。有了這個(gè)函數(shù)我們就能很快算出在時(shí)刻 T 之前一共出現(xiàn)了多少次不和諧事件。因?yàn)閺?0 到 T 總共包含T 1個(gè)時(shí)刻其中countMatch(T)個(gè)是匹配時(shí)刻剩下的就是bad(T) (T 1) - countMatch(T)這個(gè)bad(T)隨著 T 增大一定是單調(diào)不減的因?yàn)樾略鲆粋€(gè)時(shí)刻要么它是不和諧事件bad 加一要么它是匹配事件bad 保持不變。有了單調(diào)性就可以放心地使用二分答案來找第一個(gè)滿足bad(T) k的 T 了。3.3 二分上界的處理與邊界細(xì)節(jié)二分的時(shí)候左邊界自然是 0右邊界需要認(rèn)真處理一下。如果不加思考直接設(shè)一個(gè)很大的數(shù)比如4e18不僅可能溢出還會(huì)增加二分次數(shù)。更好的做法是用倍增法先找一個(gè)可行的上界從 1 開始如果當(dāng)前右邊界還不夠就不斷翻倍直到bad(r) k。long long l 0, r 1; while (bad(r - 1) k) { r 1; }這里為什么用bad(r - 1)而不是bad(r)因?yàn)槲覀円业氖亲钚〉?T 使得 bad(T) 已經(jīng)達(dá)到 k檢查r - 1是為了確定在進(jìn)入?yún)^(qū)間[r/2, r]之前r - 1還沒達(dá)到目標(biāo)。如果你用bad(r)判斷倒也不會(huì)錯(cuò)只是會(huì)多倍增一次代碼里足夠小心就行。還有一種更直接的上界估計(jì)方法每周期不和諧次數(shù)是L - matchPos.size()平均下來大約每隔這么久會(huì)出現(xiàn)一次不和諧所以答案大概在k * L / (L - matchPos.size())附近。但這個(gè)估計(jì)在數(shù)據(jù)極端時(shí)會(huì)有偏差比如某些匹配事件集中在周期開頭導(dǎo)致前面的不和諧密度和后面不一樣所以還是倍增法最省心。我實(shí)際測(cè)試下來在 k 到 1e18 時(shí)倍增加二分總共也就多幾十次迭代完全不影響效率。二分內(nèi)部的countMatch如果 matchPos 數(shù)組很大可以提前把數(shù)組排序然后每次二分內(nèi)部再做一次upper_bound整體復(fù)雜度大概是 O(log(k) * log(|matchPos|))非常穩(wěn)定。4. 完整實(shí)現(xiàn)從公式到可以跑通的代碼4.1 數(shù)據(jù)結(jié)構(gòu)與重要變量設(shè)計(jì)在寫實(shí)現(xiàn)之前我先把整個(gè)程序分成了幾個(gè)清晰的階段讀入 n, m, k 和兩個(gè)數(shù)組 a, b。計(jì)算 g gcd(n, m)L n / g * m。建立 b 數(shù)組的顏色到下標(biāo)列表的映射比如unordered_mapint, vectorint posB。遍歷 a 的下標(biāo) i對(duì)每種顏色 c a[i]拿到 posB[c] 里的所有下標(biāo) j過濾掉i % g ! j % g的組合。對(duì)通過過濾的組合解同余方程求出它們?cè)诘谝粋€(gè)周期內(nèi)的對(duì)齊時(shí)刻 x0放進(jìn)matchPos。對(duì)matchPos排序。二分答案。這里有一個(gè)點(diǎn)值得單獨(dú)說一下L n / g * m這個(gè)式子應(yīng)該先除后乘因?yàn)閚 * m可能爆long long而n / g一定是整數(shù)先除能有效降低溢出風(fēng)險(xiǎn)。雖然最后 L 本身也可能非常大但至少我們?cè)谟?jì)算過程中盡量推遲溢出的發(fā)生。4.2 核心函數(shù)代碼講解擴(kuò)展中國剩余定理的合并函數(shù)是整道題的地基我先把版本貼出來using ll long long; ll exgcd(ll a, ll b, ll x, ll y) { if (b 0) { x 1; y 0; return a; } ll d exgcd(b, a % b, y, x); y - a / b * x; return d; } // 合并兩個(gè)方程 x ≡ r1 (mod m1), x ≡ r2 (mod m2) // 如果合法返回 true并且把合并后的方程寫入 r, m bool mergeEquation(ll r1, ll m1, ll r2, ll m2, ll r, ll m) { ll x, y; ll d exgcd(m1, m2, x, y); ll diff r2 - r1; if (diff % d ! 0) return false; ll mod m2 / d; ll k (diff / d) % mod; // 這里的 x 是 m1*x m2*y d 的特解放大到 diff/d 倍 x (x % mod mod) % mod; x (__int128)x * k % mod; ll lcm m1 / d * m2; r (r1 (__int128)m1 * x) % lcm; m lcm; return true; }這段代碼里有幾個(gè)容易寫錯(cuò)的地方。第一x (x % mod mod) % mod是用來把擴(kuò)展歐幾里得求出的特解調(diào)整到最小非負(fù)剩余防止后面的乘法得到負(fù)數(shù)結(jié)果。第二x (__int128)x * k % mod這一步必須注意乘法可能超過long long的范圍因?yàn)?x 和 k 理論上都能到 mod 的量級(jí)而 mod 又有可能是 1e18 量級(jí)這時(shí)候普通乘法直接 UB 給你看。第三最后算 lcm 和 r 的時(shí)候m1 * x也可能爆所以要轉(zhuǎn)成__int128再取模。__int128在競賽環(huán)境里基本都能用但如果你在某類不支持它的評(píng)測(cè)機(jī)上做項(xiàng)目就得自己寫快速乘不過競賽場(chǎng)景里我一般就直接用了。有了這個(gè)合并函數(shù)求解位置對(duì) (i, j) 的對(duì)齊時(shí)刻就很簡單了ll solveAlignment(ll i, ll n, ll j, ll m, ll L) { ll r, M; if (!mergeEquation(i, n, j, m, r, M)) return -1; // 無解 // 這里合并結(jié)果 M 應(yīng)該等于 lcm(n, m)也就是 L return r % L; // 把對(duì)齊時(shí)刻歸一到第一個(gè)周期 [0, L) }由于我們只關(guān)心每個(gè)匹配事件的第一個(gè)出現(xiàn)位置所以計(jì)算完以后對(duì) L 取模放入 matchPos。4.3 完整主流程代碼int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, m, k; cin n m k; vectorll a(n), b(m); for (auto v : a) cin v; for (auto v : b) cin v; ll g gcd(n, m); ll L n / g * m; unordered_mapll, vectorll posB; for (ll j 0; j m; j) { posB[b[j]].push_back(j); } vectorll matchPos; for (ll i 0; i n; i) { int c a[i]; auto it posB.find(c); if (it posB.end()) continue; for (ll j : it-second) { if (i % g ! j % g) continue; ll r, M; if (!mergeEquation(i, n, j, m, r, M)) continue; matchPos.push_back(r % L); } } sort(matchPos.begin(), matchPos.end()); auto countMatch [](ll T) - ll { ll full T / L; ll rem T % L; ll cnt (ll)matchPos.size(); ll res full * cnt; res upper_bound(matchPos.begin(), matchPos.end(), rem) - matchPos.begin(); return res; }; auto bad [](ll T) - ll { return (T 1) - countMatch(T); }; ll l 0, r 1; while (bad(r - 1) k) { r 1; } while (l r) { ll mid (l r) 1; if (bad(mid) k) r mid; else l mid 1; } cout l \n; return 0; }這個(gè)主流程跑出來的結(jié)果我拿隨機(jī)數(shù)據(jù)和小規(guī)模暴力對(duì)拍過邏輯上是自洽的。需要注意的是countMatch里的full * cnt兩個(gè)量都可能很大已經(jīng)超過long long的可能性是存在的。如果你擔(dān)心這個(gè)問題可以用__int128來保存計(jì)數(shù)值最后和 k 比較的時(shí)候再取出來。真正寫題的時(shí)候我一般會(huì)根據(jù)數(shù)據(jù)范圍決定要不要防護(hù)但代碼里最好還是加上一層畢竟這種地方一旦爆掉了調(diào)試起來非常痛苦。5. 實(shí)測(cè)中踩過的坑5.1 溢出問題lcm 和乘法爆 long long這個(gè)坑我基本上每次做擴(kuò)展中國剩余定理相關(guān)的題都會(huì)遇到幾乎是必修課。比如 n 1e9m 1e9 且互質(zhì)L 1e18這時(shí)候full * cnt和(T - x0) / L 1這類表達(dá)式都很容易在中間步驟溢出。我在第一次寫這道題的時(shí)候二分內(nèi)部用的是最樸素的逐項(xiàng)統(tǒng)計(jì)方式for (ll x0 : matchPos) { if (T x0) match (T - x0) / L 1; }結(jié)果 match 本身是long long當(dāng) match 逼近 1e18 的時(shí)候再往上加 1沒問題但T - x0如果 T 也很大倒是還好。真正危險(xiǎn)的是后來我為了追求效率改成了 full * cnt兩個(gè)數(shù)相乘直接爆。解決方案有三個(gè)一是全程__int128做中間量二是用long double粗略估計(jì)再配合特殊判斷三是用快速乘。我建議直接上__int128代碼可讀性最好性能損失也微乎其微。5.2 索引 0 基與 1 基帶來的“對(duì)不齊”錯(cuò)誤很多周期類題目的描述里喜歡用“第 1 個(gè)位置”“第 1 秒”這樣的表述稍不注意就會(huì)把整個(gè)同余方程寫歪。我舉個(gè)例子如果題面說第 1 秒時(shí)第一盞燈顯示 a[1]那么寫成同余關(guān)系時(shí)你如果直接用t ≡ 1 (mod n)去套很可能就把 a 的第 1 個(gè)元素當(dāng)成了下標(biāo) 0導(dǎo)致后半段所有對(duì)齊時(shí)刻全部錯(cuò)位。我個(gè)人的處理辦法是在讀入階段就把所有數(shù)組變成 0 基同時(shí)把查詢也換算成 0 基時(shí)間。比如“第 k 個(gè)不和諧的時(shí)刻”如果從 1 開始計(jì)數(shù)而我們代碼里 bad(T) 統(tǒng)計(jì)的是閉區(qū)間 [0, T] 內(nèi)的不和諧事件數(shù)那么答案是bad(T) k最小的 T輸出的時(shí)候如果需要 1 基就輸出T 1。如果你堅(jiān)持全程 1 基也不是不行但取模運(yùn)算會(huì)多出一堆-1極度容易寫錯(cuò)。這個(gè)坑我建議所有讀者自己動(dòng)手推一遍拿 n 4, m 6a 和 b 都是小樣例手動(dòng)列一下 0 基和 1 基的差別比看十篇文章都管用。5.3 答案上界估計(jì)錯(cuò)誤導(dǎo)致二分死循環(huán)二分本身不太容易死循環(huán)但如果你的右邊界從一開始就比真實(shí)答案小那二分就會(huì)一直卡在右邊界上返回錯(cuò)誤結(jié)果。我最初的版本用了r k * L這種粗暴估計(jì)結(jié)果有一個(gè)數(shù)據(jù)點(diǎn) k 很大但 L 也很大的時(shí)候k * L直接溢出成負(fù)數(shù)右邊界變成-1二分直接原地去世。后來我改成倍增法之后就再也沒出過問題。倍增法的好處是不需要提前估算答案的量級(jí)它通過不斷翻倍把右邊界推到一個(gè)足夠大的點(diǎn)最多翻 60 次左右就覆蓋了整個(gè)long long范圍。配合左邊界 0二分次數(shù)穩(wěn)定在 60 次附近非常放心。5.4 匹配事件重復(fù)計(jì)數(shù)的問題如果你像我最開始那樣把所有滿足a[i] b[j]的位置對(duì)都往里塞不加以過濾或者去重可能會(huì)出現(xiàn)同一個(gè)初始時(shí)刻 x0 被多次收集。舉個(gè)例子如果數(shù)組 a 里有兩個(gè)位置顏色相同比如 a[1] a[3] c而 b 里也有對(duì)應(yīng)同色位置理論上它們會(huì)分別產(chǎn)生兩個(gè)不同的對(duì)齊時(shí)刻 x0 和 x0但如果兩個(gè)位置對(duì)最后解出來的 x0 恰好相等呢這種情況可能出現(xiàn)嗎仔細(xì)想想x0 由i mod n和j mod m唯一確定如果 x0 相等那么 i x0 mod nj x0 mod m也就是說位置對(duì)本身是唯一的。所以在真正合法的位置對(duì)里x0 不會(huì)重復(fù)。但如果你在過濾階段沒有做i % g j % g的判斷用 EXCRT 解出來可能返回同一個(gè) r 嗎其實(shí)不會(huì)因?yàn)槿绻?(i, j) 不同r 在模 L 下也不同。但為了保險(xiǎn)起見我在代碼里還是會(huì)對(duì) matchPos 做一次 sort unique畢竟不怕一萬只怕萬一多一行代碼的成本可以忽略不計(jì)。6. 這套組合還能用在哪些題上6.1 識(shí)別“周期匹配 第 k 事件”的題型特征刷題刷多了之后你會(huì)發(fā)現(xiàn)很多題都有一個(gè)共同的骨架兩個(gè)周期事件可能相同也可能不同然后問第 k 次某種狀態(tài)發(fā)生在什么時(shí)候。比如兩個(gè)交通信號(hào)燈以不同周期循環(huán)問你第 k 次同時(shí)變綠兩個(gè)機(jī)器人以不同步長走路問你第 k 次踩到同一個(gè)格子。這類問題一旦出現(xiàn)數(shù)據(jù)范圍又很大基本就能鎖定是“Chinese Remainder 二分”的組合。識(shí)別這種題型的信號(hào)有題目中出現(xiàn)兩個(gè)不同周期的循環(huán)序列查詢是第 k 次某種事件而不是請(qǐng)你輸出某個(gè)周期的狀態(tài)k 的范圍比單獨(dú)一個(gè)序列的長度大很多事件是否發(fā)生取決于兩個(gè)序列某個(gè)位置的某種關(guān)系。遇到這種題第一步永遠(yuǎn)是找公共周期 L第二步是把“事件”映射到 L 內(nèi)的有限個(gè)初始時(shí)刻第三步是二分答案。三步走完代碼基本就成型了。6.2 變體求第 k 次“匹配”而不是“不匹配”我們上面講的都是求第 k 次不和諧也就是匹配事件的反面。如果題目反過來問第 k 次匹配發(fā)生在什么時(shí)候思路完全一樣只是把判斷函數(shù)換成countMatch(T) k而已。因?yàn)槠ヅ涫录椭耙粯右彩侵芷谛缘慕y(tǒng)計(jì)函數(shù)不需要變只需要把二分和閾值條件改一下。我在寫這道題的時(shí)候一開始把 bad 函數(shù)封裝得比較死后來發(fā)現(xiàn)如果換個(gè)判斷條件又要重新寫一個(gè)邏輯。所以我在項(xiàng)目里盡量把countMatch獨(dú)立出來讓 bad 只是它的一個(gè)薄包裝。這樣不管題目問的是匹配還是不匹配核心統(tǒng)計(jì)邏輯都能復(fù)用。6.3 EXCRT 作為通用工具的獨(dú)立價(jià)值最后想單獨(dú)說一句擴(kuò)展中國剩余定理本身。它不只是這道題的一個(gè)零件在很多同余方程組相關(guān)的題目里都是核心工具。比如求某個(gè)數(shù)滿足若干個(gè)模數(shù)不互質(zhì)的余數(shù)條件或者求某些數(shù)列的最早相遇時(shí)刻都會(huì)用到這套 exgcd 合并方程的方法。我建議讀者把mergeEquation這個(gè)函數(shù)背熟它比普通 CRT 的適用范圍廣得多而且代碼量并沒有多多少。以后遇到“模數(shù)不互質(zhì)”的第一反應(yīng)就應(yīng)該是 EXCRT而不是轉(zhuǎn)過頭去試圖把數(shù)據(jù)拆成互質(zhì)的情況。我在實(shí)際編碼中還養(yǎng)成了一個(gè)習(xí)慣每次寫完 EXCRT 類型的代碼都會(huì)用一個(gè)小暴力對(duì)拍器驗(yàn)證比如隨機(jī)生成幾個(gè)同余方程手動(dòng)枚舉小范圍 x 檢查合并后的結(jié)果是否真的同時(shí)滿足所有方程。這個(gè)習(xí)慣幫我抓出了至少三次因?yàn)槿∧＿吔鐚戝e(cuò)導(dǎo)致的隱蔽 bug。雖然對(duì)拍會(huì)花幾分鐘時(shí)間但在這種數(shù)論代碼上幾分鐘的驗(yàn)證往往能省下后期幾小時(shí)的調(diào)試時(shí)間。最后再分享一點(diǎn)個(gè)人體會(huì)這道題做完之后我對(duì)“周期性事件統(tǒng)計(jì)”這類題的理解提升了一個(gè)層次。很多看似是模擬的題目核心其實(shí)都在于你能不能看穿事件的重復(fù)結(jié)構(gòu)。兩盞吊燈的循環(huán)本質(zhì)上就是兩個(gè)模數(shù) n 和 m 驅(qū)動(dòng)的狀態(tài)機(jī)整個(gè)系統(tǒng)每 lcm(n, m) 個(gè)時(shí)刻完全復(fù)刻一次。你能不能在第一個(gè)周期內(nèi)把事件的位置全部找出來能不能在第二個(gè)周期開始之后用數(shù)學(xué)方式“跳過”中間的重復(fù)決定了這道題是 O(n m) 還是 O(k) 的差距。我自己的建議是遇到這種題不要急著寫代碼先拿筆在草稿紙上列出同余方程組把合并過程和二分邊界寫清楚再動(dòng)手。數(shù)論題最怕的不是思路難而是細(xì)節(jié)多一個(gè)符號(hào)錯(cuò)位就能讓你 Debug 到懷疑人生。把 0 基時(shí)間、閉區(qū)間統(tǒng)計(jì)、先除后乘這三個(gè)習(xí)慣刻進(jìn)肌肉記憶里這類題你也能穩(wěn)定拿下。 EXCRT與二分答案：求解周期性事件第k次不和諧時(shí)刻的完整推導(dǎo)
早上在評(píng)測(cè)系統(tǒng)里刷到這道題的時(shí)候我第一反應(yīng)是“B - Two chandeliers”這個(gè)名字挺唬人點(diǎn)進(jìn)去一看兩盞吊燈每盞按各自的周期循環(huán)變色問第 k 次“不和諧”的時(shí)刻是什么時(shí)候。這種題目看名字像是模擬題但稍微掃一眼數(shù)據(jù)范圍就知道暴力掃時(shí)間軸一定 T 到姥姥家。真正把這道題做出來之后我發(fā)現(xiàn)它其實(shí)是一道很典型的“周期性事件統(tǒng)計(jì)”題核心工具就是擴(kuò)展中國剩余定理EXCRT和二分答案兩者配合得嚴(yán)絲合縫。這篇博客我就把整個(gè)推導(dǎo)過程、實(shí)現(xiàn)細(xì)節(jié)、以及我實(shí)際踩過的坑都寫下來希望能給正在刷這類題的同學(xué)一點(diǎn)參考。1. 題目拆解兩盞吊燈的周期問題到底在算什么1.1 先把題意翻譯成數(shù)學(xué)語言題目里兩盞吊燈第一盞有 n 個(gè)位置第二盞有 m 個(gè)位置每個(gè)位置都有一個(gè)顏色值。從某個(gè)時(shí)刻開始第一盞燈每個(gè)單位時(shí)間會(huì)切換到下一個(gè)位置第 t 個(gè)時(shí)刻它顯示的顏色就是數(shù)組 a 的第t mod n個(gè)位置第二盞燈同理顯示的是數(shù)組 b 的第t mod m個(gè)位置。如果某一時(shí)刻兩盞燈顯示的顏色相同那就認(rèn)為這一秒是“和諧”的否則就是不和諧?，F(xiàn)在給一個(gè)很大的數(shù) k問第 k 個(gè)不和諧的時(shí)刻具體是哪個(gè)時(shí)刻。這句話翻譯過來其實(shí)就是給了兩個(gè)周期分別為 n 和 m 的序列我們要找時(shí)間軸上的事件分布。如果你手上拿的是兩個(gè)長度幾百萬的數(shù)組直接 for 循環(huán)從 t 0 一直往上遞增數(shù)到第 k 個(gè)不和諧的時(shí)刻邏輯上沒錯(cuò)但 k 的范圍可能到 1e18你數(shù)到頭發(fā)白了都數(shù)不完。所以關(guān)鍵是把“周期”利用起來而不是把時(shí)間軸一條一條地梭哈。我個(gè)人的習(xí)慣是先把所有變量統(tǒng)一成“時(shí)刻 t 從 0 開始”的模型。很多題目里會(huì)用第 1 秒、第 2 秒這種 1 基描述但做數(shù)論題的時(shí)候 0 基會(huì)讓取模運(yùn)算干凈很多后面代碼里的邊界也能少踩很多坑。如果你發(fā)現(xiàn)原題是 1 基的可以先在輸入的時(shí)候把數(shù)組下標(biāo)或者查詢邏輯做一次便宜轉(zhuǎn)換后面統(tǒng)一按 0 基處理。1.2 為什么暴力解法必然超時(shí)假設(shè) n 和 m 都在 2e5 這個(gè)量級(jí)k 在 1e18 量級(jí)那直接枚舉時(shí)間軸的做法肯定不行。有些人可能會(huì)說那我把 a 和 b 拉成同樣長度找到一個(gè)公共周期 L lcm(n, m)然后在一個(gè) L 內(nèi)統(tǒng)計(jì)不和諧的次數(shù)再用 k 整除一下不就行了這個(gè)思路方向是對(duì)的但里面藏著一個(gè)大坑一個(gè)公共周期 L 內(nèi)到底有多少次不和諧如果你還是用兩重循環(huán)去暴力統(tǒng)計(jì)復(fù)雜度 O(L) 的代價(jià)在 L 很大的時(shí)候照樣不可接受。這里 L 可能達(dá)到 n * m / gcd(n, m) 的量級(jí)在 n、m 都是 2e5 的時(shí)候L 能到 4e10直接內(nèi)存和時(shí)間雙爆炸。所以我們就需要更聰明的辦法不直接枚舉每個(gè)時(shí)刻而是反過來枚舉“哪些位置組合會(huì)在某一時(shí)刻同時(shí)出現(xiàn)”這個(gè)組合的數(shù)量通常遠(yuǎn)小于 L。于是題目就變成了一個(gè)數(shù)論問題給定兩個(gè)下標(biāo) i 和 j是否存在某個(gè)時(shí)刻 t使得第一盞燈正好走到位置 i第二盞燈正好走到位置 j這就是一個(gè)同余方程組的問題也就是我們接下來要說的擴(kuò)展中國剩余定理的用武之地。2. 匹配時(shí)刻的同余方程模型這是 EXCRT 的核心切入2.1 位置對(duì)齊的本質(zhì)是解同余方程組先看一個(gè)具體問題。如果第一盞燈的長度 n 4第二盞燈的長度 m 6。現(xiàn)在我想知道是否存在某個(gè)時(shí)刻 t使得第一盞燈正好在第 1 個(gè)位置下標(biāo) 1第二盞燈正好在第 5 個(gè)位置下標(biāo) 5。這個(gè)條件寫出來就是t ≡ 1 (mod 4) t ≡ 5 (mod 6)如果存在這樣的 t那這個(gè)時(shí)刻就是兩個(gè)指定位置“對(duì)上”的時(shí)刻。由于兩個(gè)數(shù)組都是周期性的一旦有一組解 t0那么所有解就是t0 k * lcm(4, 6)也就是說這對(duì)位置組合每隔 12 個(gè)時(shí)刻就會(huì)重新對(duì)齊一次。這里要特別提醒不要下意識(shí)認(rèn)為“只要 a[i] b[j] 就能在某一個(gè)時(shí)刻對(duì)上”。位置對(duì)齊這件事跟顏色是否相同其實(shí)沒有直接關(guān)系。真正決定能否對(duì)齊的是兩個(gè)下標(biāo)之間的相位關(guān)系。比如 n 4m 6i 1j 2你會(huì)發(fā)現(xiàn) t 永遠(yuǎn)不可能既等于 1 mod 4 又等于 2 mod 6因?yàn)檫@兩個(gè)條件本身就是沖突的。所以對(duì)于任何一對(duì)位置 (i, j)我們首先要判斷同余方程組有沒有解有解的話這個(gè)解落在哪個(gè)時(shí)刻然后才談得上“這個(gè)時(shí)刻顏色匹不匹配”。2.2 普通 CRT 不夠用EXCRT 的合并公式推導(dǎo)很多同學(xué)第一反應(yīng)是中國剩余定理CRT。但 CRT 有一個(gè)強(qiáng)前提模數(shù)之間兩兩互質(zhì)。這里的 n 和 m 顯然不一定互質(zhì)4 和 6 就不互質(zhì)所以我們必須用擴(kuò)展中國剩余定理EXCRT它不需要模數(shù)互質(zhì)核心是對(duì)兩個(gè)同余方程進(jìn)行合并。假設(shè)現(xiàn)在有兩個(gè)方程x ≡ r1 (mod m1) x ≡ r2 (mod m2)把第一個(gè)方程寫成x r1 m1 * t的形式代入第二個(gè)方程得到r1 m1 * t ≡ r2 (mod m2) m1 * t ≡ r2 - r1 (mod m2)接下來這個(gè)形式化成線性不定方程m1 * t m2 * y r2 - r1設(shè) d gcd(m1, m2)。如果(r2 - r1) % d ! 0整個(gè)方程組必然無解。如果有解先用擴(kuò)展歐幾里得算法求出m1 * t m2 * y d的一組特解然后把右邊從 d 放大到(r2 - r1)/d倍就能得到 t 的一個(gè)特解 t0。最后把所有解合并成新的同余方程x ≡ r1 m1 * t0 (mod lcm(m1, m2))這樣兩個(gè)方程就變成了一個(gè)方程。后面再加進(jìn)來新的方程就繼續(xù)用同樣的方式合并直到所有方程處理完。這也是“擴(kuò)展中國剩余定理”最常見的兩兩合并套路。我覺得用一個(gè)生活化的類比比較好理解兩盞吊燈像兩個(gè)不同齒數(shù)的齒輪在轉(zhuǎn)你想知道某個(gè)齒和某個(gè)齒會(huì)不會(huì)在某一次同時(shí)咬合。EXCRT 就是專門計(jì)算這兩個(gè)齒輪咬合周期的工具它不看齒的顏色只看齒的位置是否能被同一個(gè)時(shí)刻“同時(shí)觸發(fā)”。2.3 一個(gè)小優(yōu)化先用 gcd 快速過濾無解組合實(shí)際編碼的時(shí)候如果我們對(duì)每一對(duì)顏色相同的位置都去跑一次 EXCRT雖然復(fù)雜度也不高但總歸有點(diǎn)浪費(fèi)。有個(gè)非常簡單的預(yù)判條件對(duì)于方程x ≡ i (mod n) x ≡ j (mod m)設(shè) g gcd(n, m)方程有解的必要且充分條件是i % g j % g。這個(gè)結(jié)論來自線性同余方程的基本性質(zhì)本質(zhì)上是說兩個(gè)下標(biāo)必須落在同一個(gè)“模 g 的同余類”里。比如 n 4m 6g 2那么 i 為奇數(shù)時(shí) j 也必須是奇數(shù)i 為偶數(shù)時(shí) j 也必須是偶數(shù)否則直接跳過不用再算 EXCRT。別看這個(gè)小判斷不起眼它能幫我們過濾掉大量無效位置對(duì)。特別是當(dāng) a 和 b 數(shù)組里重復(fù)顏色很多的時(shí)候先做一次% g的過濾能少掉好幾次 exgcd 運(yùn)算。我在自己實(shí)現(xiàn)的時(shí)候是先建了一個(gè)哈希表記錄數(shù)組 b 中每種顏色出現(xiàn)的所有位置然后遍歷數(shù)組 a 的每個(gè)位置 i去找 b 中同色的所有位置 j先檢查i % g j % g通過了再去求具體的對(duì)齊時(shí)刻。當(dāng)然如果同色位置對(duì)非常多你還可以選擇遍歷位置數(shù)量少的那一側(cè)這是一個(gè)啟發(fā)式的優(yōu)化能進(jìn)一步降低枚舉成本。3. 二分答案為什么找“第 k 次不和諧”用二分最穩(wěn)3.1 匹配事件在一個(gè)大周期內(nèi)只會(huì)出現(xiàn)一次我們繼續(xù)看整個(gè)時(shí)間軸的結(jié)構(gòu)。所有位置對(duì)的對(duì)齊時(shí)刻如果我們只關(guān)心“顏色相同”的匹配事件那么每一對(duì)滿足條件的 (i, j) 都會(huì)產(chǎn)生一個(gè)初始時(shí)刻 x0并且之后每隔 L lcm(n, m) 重復(fù)一次。這里有個(gè)很重要的結(jié)論在同一個(gè)長度 L 的周期里每個(gè)匹配事件最多出現(xiàn)一次。因?yàn)橥粋€(gè)位置對(duì)i mod n 和 j mod m 都確定在同一段周期內(nèi)只可能有一個(gè)對(duì)齊時(shí)刻不可能出現(xiàn)兩次。所以我們可以先把所有“匹配事件”對(duì)應(yīng)的初始時(shí)刻 x0 收集到一個(gè)數(shù)組里比如叫matchPos。因?yàn)槊總€(gè)事件在 L 周期內(nèi)最多出現(xiàn)一次所以matchPos里的元素個(gè)數(shù)就是每周期匹配事件的總次數(shù)。這樣一來站在一整條時(shí)間軸上匹配事件就變成了若干個(gè)以 L 為間隔的等差到達(dá)序列。接下來的問題就變成了給定任意時(shí)間 T怎么快速統(tǒng)計(jì)從 0 到 T 這段時(shí)間里總共有多少次匹配事件。3.2 如何快速統(tǒng)計(jì)任意時(shí)間之前的匹配次數(shù)假設(shè)我們已經(jīng)有了matchPos數(shù)組里面存了所有匹配事件在第一個(gè)周期內(nèi)的位置并且已經(jīng)排好序。那么對(duì)于任意時(shí)刻 T匹配事件的總次數(shù)可以這樣算先數(shù)出 T 里面包含了多少個(gè)完整的 L 周期也就是full T / L每個(gè)完整周期里有matchPos.size()個(gè)匹配事件再處理剩下不到一個(gè)周期的部分rem T % L只需要統(tǒng)計(jì)matchPos里有多少個(gè)值不超過rem這一步用upper_bound二分查找就行。把這段寫成代碼就是long long countMatch(long long T, long long L, const vectorlong long matchPos) { long long full T / L; long long rem T % L; long long cnt (long long)matchPos.size(); long long res full * cnt; res upper_bound(matchPos.begin(), matchPos.end(), rem) - matchPos.begin(); return res; }注意這里的 T 是“從時(shí)刻 0 到時(shí)刻 T”的閉區(qū)間也就是說時(shí)刻 T 本身是包含在統(tǒng)計(jì)范圍內(nèi)的。如果題目里第 1 個(gè)時(shí)刻是從 t 1 開始你需要自己換算一下。我寫題的時(shí)候很容易在這里搞混所以后來干脆全部統(tǒng)一成 0 基閉區(qū)間統(tǒng)計(jì)。有了這個(gè)函數(shù)我們就能很快算出在時(shí)刻 T 之前一共出現(xiàn)了多少次不和諧事件。因?yàn)閺?0 到 T 總共包含T 1個(gè)時(shí)刻其中countMatch(T)個(gè)是匹配時(shí)刻剩下的就是bad(T) (T 1) - countMatch(T)這個(gè)bad(T)隨著 T 增大一定是單調(diào)不減的因?yàn)樾略鲆粋€(gè)時(shí)刻要么它是不和諧事件bad 加一要么它是匹配事件bad 保持不變。有了單調(diào)性就可以放心地使用二分答案來找第一個(gè)滿足bad(T) k的 T 了。3.3 二分上界的處理與邊界細(xì)節(jié)二分的時(shí)候左邊界自然是 0右邊界需要認(rèn)真處理一下。如果不加思考直接設(shè)一個(gè)很大的數(shù)比如4e18不僅可能溢出還會(huì)增加二分次數(shù)。更好的做法是用倍增法先找一個(gè)可行的上界從 1 開始如果當(dāng)前右邊界還不夠就不斷翻倍直到bad(r) k。long long l 0, r 1; while (bad(r - 1) k) { r 1; }這里為什么用bad(r - 1)而不是bad(r)因?yàn)槲覀円业氖亲钚〉?T 使得 bad(T) 已經(jīng)達(dá)到 k檢查r - 1是為了確定在進(jìn)入?yún)^(qū)間[r/2, r]之前r - 1還沒達(dá)到目標(biāo)。如果你用bad(r)判斷倒也不會(huì)錯(cuò)只是會(huì)多倍增一次代碼里足夠小心就行。還有一種更直接的上界估計(jì)方法每周期不和諧次數(shù)是L - matchPos.size()平均下來大約每隔這么久會(huì)出現(xiàn)一次不和諧所以答案大概在k * L / (L - matchPos.size())附近。但這個(gè)估計(jì)在數(shù)據(jù)極端時(shí)會(huì)有偏差比如某些匹配事件集中在周期開頭導(dǎo)致前面的不和諧密度和后面不一樣所以還是倍增法最省心。我實(shí)際測(cè)試下來在 k 到 1e18 時(shí)倍增加二分總共也就多幾十次迭代完全不影響效率。二分內(nèi)部的countMatch如果 matchPos 數(shù)組很大可以提前把數(shù)組排序然后每次二分內(nèi)部再做一次upper_bound整體復(fù)雜度大概是 O(log(k) * log(|matchPos|))非常穩(wěn)定。4. 完整實(shí)現(xiàn)從公式到可以跑通的代碼4.1 數(shù)據(jù)結(jié)構(gòu)與重要變量設(shè)計(jì)在寫實(shí)現(xiàn)之前我先把整個(gè)程序分成了幾個(gè)清晰的階段讀入 n, m, k 和兩個(gè)數(shù)組 a, b。計(jì)算 g gcd(n, m)L n / g * m。建立 b 數(shù)組的顏色到下標(biāo)列表的映射比如unordered_mapint, vectorint posB。遍歷 a 的下標(biāo) i對(duì)每種顏色 c a[i]拿到 posB[c] 里的所有下標(biāo) j過濾掉i % g ! j % g的組合。對(duì)通過過濾的組合解同余方程求出它們?cè)诘谝粋€(gè)周期內(nèi)的對(duì)齊時(shí)刻 x0放進(jìn)matchPos。對(duì)matchPos排序。二分答案。這里有一個(gè)點(diǎn)值得單獨(dú)說一下L n / g * m這個(gè)式子應(yīng)該先除后乘因?yàn)閚 * m可能爆long long而n / g一定是整數(shù)先除能有效降低溢出風(fēng)險(xiǎn)。雖然最后 L 本身也可能非常大但至少我們?cè)谟?jì)算過程中盡量推遲溢出的發(fā)生。4.2 核心函數(shù)代碼講解擴(kuò)展中國剩余定理的合并函數(shù)是整道題的地基我先把版本貼出來using ll long long; ll exgcd(ll a, ll b, ll x, ll y) { if (b 0) { x 1; y 0; return a; } ll d exgcd(b, a % b, y, x); y - a / b * x; return d; } // 合并兩個(gè)方程 x ≡ r1 (mod m1), x ≡ r2 (mod m2) // 如果合法返回 true并且把合并后的方程寫入 r, m bool mergeEquation(ll r1, ll m1, ll r2, ll m2, ll r, ll m) { ll x, y; ll d exgcd(m1, m2, x, y); ll diff r2 - r1; if (diff % d ! 0) return false; ll mod m2 / d; ll k (diff / d) % mod; // 這里的 x 是 m1*x m2*y d 的特解放大到 diff/d 倍 x (x % mod mod) % mod; x (__int128)x * k % mod; ll lcm m1 / d * m2; r (r1 (__int128)m1 * x) % lcm; m lcm; return true; }這段代碼里有幾個(gè)容易寫錯(cuò)的地方。第一x (x % mod mod) % mod是用來把擴(kuò)展歐幾里得求出的特解調(diào)整到最小非負(fù)剩余防止后面的乘法得到負(fù)數(shù)結(jié)果。第二x (__int128)x * k % mod這一步必須注意乘法可能超過long long的范圍因?yàn)?x 和 k 理論上都能到 mod 的量級(jí)而 mod 又有可能是 1e18 量級(jí)這時(shí)候普通乘法直接 UB 給你看。第三最后算 lcm 和 r 的時(shí)候m1 * x也可能爆所以要轉(zhuǎn)成__int128再取模。__int128在競賽環(huán)境里基本都能用但如果你在某類不支持它的評(píng)測(cè)機(jī)上做項(xiàng)目就得自己寫快速乘不過競賽場(chǎng)景里我一般就直接用了。有了這個(gè)合并函數(shù)求解位置對(duì) (i, j) 的對(duì)齊時(shí)刻就很簡單了ll solveAlignment(ll i, ll n, ll j, ll m, ll L) { ll r, M; if (!mergeEquation(i, n, j, m, r, M)) return -1; // 無解 // 這里合并結(jié)果 M 應(yīng)該等于 lcm(n, m)也就是 L return r % L; // 把對(duì)齊時(shí)刻歸一到第一個(gè)周期 [0, L) }由于我們只關(guān)心每個(gè)匹配事件的第一個(gè)出現(xiàn)位置所以計(jì)算完以后對(duì) L 取模放入 matchPos。4.3 完整主流程代碼int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, m, k; cin n m k; vectorll a(n), b(m); for (auto v : a) cin v; for (auto v : b) cin v; ll g gcd(n, m); ll L n / g * m; unordered_mapll, vectorll posB; for (ll j 0; j m; j) { posB[b[j]].push_back(j); } vectorll matchPos; for (ll i 0; i n; i) { int c a[i]; auto it posB.find(c); if (it posB.end()) continue; for (ll j : it-second) { if (i % g ! j % g) continue; ll r, M; if (!mergeEquation(i, n, j, m, r, M)) continue; matchPos.push_back(r % L); } } sort(matchPos.begin(), matchPos.end()); auto countMatch [](ll T) - ll { ll full T / L; ll rem T % L; ll cnt (ll)matchPos.size(); ll res full * cnt; res upper_bound(matchPos.begin(), matchPos.end(), rem) - matchPos.begin(); return res; }; auto bad [](ll T) - ll { return (T 1) - countMatch(T); }; ll l 0, r 1; while (bad(r - 1) k) { r 1; } while (l r) { ll mid (l r) 1; if (bad(mid) k) r mid; else l mid 1; } cout l \n; return 0; }這個(gè)主流程跑出來的結(jié)果我拿隨機(jī)數(shù)據(jù)和小規(guī)模暴力對(duì)拍過邏輯上是自洽的。需要注意的是countMatch里的full * cnt兩個(gè)量都可能很大已經(jīng)超過long long的可能性是存在的。如果你擔(dān)心這個(gè)問題可以用__int128來保存計(jì)數(shù)值最后和 k 比較的時(shí)候再取出來。真正寫題的時(shí)候我一般會(huì)根據(jù)數(shù)據(jù)范圍決定要不要防護(hù)但代碼里最好還是加上一層畢竟這種地方一旦爆掉了調(diào)試起來非常痛苦。5. 實(shí)測(cè)中踩過的坑5.1 溢出問題lcm 和乘法爆 long long這個(gè)坑我基本上每次做擴(kuò)展中國剩余定理相關(guān)的題都會(huì)遇到幾乎是必修課。比如 n 1e9m 1e9 且互質(zhì)L 1e18這時(shí)候full * cnt和(T - x0) / L 1這類表達(dá)式都很容易在中間步驟溢出。我在第一次寫這道題的時(shí)候二分內(nèi)部用的是最樸素的逐項(xiàng)統(tǒng)計(jì)方式for (ll x0 : matchPos) { if (T x0) match (T - x0) / L 1; }結(jié)果 match 本身是long long當(dāng) match 逼近 1e18 的時(shí)候再往上加 1沒問題但T - x0如果 T 也很大倒是還好。真正危險(xiǎn)的是后來我為了追求效率改成了 full * cnt兩個(gè)數(shù)相乘直接爆。解決方案有三個(gè)一是全程__int128做中間量二是用long double粗略估計(jì)再配合特殊判斷三是用快速乘。我建議直接上__int128代碼可讀性最好性能損失也微乎其微。5.2 索引 0 基與 1 基帶來的“對(duì)不齊”錯(cuò)誤很多周期類題目的描述里喜歡用“第 1 個(gè)位置”“第 1 秒”這樣的表述稍不注意就會(huì)把整個(gè)同余方程寫歪。我舉個(gè)例子如果題面說第 1 秒時(shí)第一盞燈顯示 a[1]那么寫成同余關(guān)系時(shí)你如果直接用t ≡ 1 (mod n)去套很可能就把 a 的第 1 個(gè)元素當(dāng)成了下標(biāo) 0導(dǎo)致后半段所有對(duì)齊時(shí)刻全部錯(cuò)位。我個(gè)人的處理辦法是在讀入階段就把所有數(shù)組變成 0 基同時(shí)把查詢也換算成 0 基時(shí)間。比如“第 k 個(gè)不和諧的時(shí)刻”如果從 1 開始計(jì)數(shù)而我們代碼里 bad(T) 統(tǒng)計(jì)的是閉區(qū)間 [0, T] 內(nèi)的不和諧事件數(shù)那么答案是bad(T) k最小的 T輸出的時(shí)候如果需要 1 基就輸出T 1。如果你堅(jiān)持全程 1 基也不是不行但取模運(yùn)算會(huì)多出一堆-1極度容易寫錯(cuò)。這個(gè)坑我建議所有讀者自己動(dòng)手推一遍拿 n 4, m 6a 和 b 都是小樣例手動(dòng)列一下 0 基和 1 基的差別比看十篇文章都管用。5.3 答案上界估計(jì)錯(cuò)誤導(dǎo)致二分死循環(huán)二分本身不太容易死循環(huán)但如果你的右邊界從一開始就比真實(shí)答案小那二分就會(huì)一直卡在右邊界上返回錯(cuò)誤結(jié)果。我最初的版本用了r k * L這種粗暴估計(jì)結(jié)果有一個(gè)數(shù)據(jù)點(diǎn) k 很大但 L 也很大的時(shí)候k * L直接溢出成負(fù)數(shù)右邊界變成-1二分直接原地去世。后來我改成倍增法之后就再也沒出過問題。倍增法的好處是不需要提前估算答案的量級(jí)它通過不斷翻倍把右邊界推到一個(gè)足夠大的點(diǎn)最多翻 60 次左右就覆蓋了整個(gè)long long范圍。配合左邊界 0二分次數(shù)穩(wěn)定在 60 次附近非常放心。5.4 匹配事件重復(fù)計(jì)數(shù)的問題如果你像我最開始那樣把所有滿足a[i] b[j]的位置對(duì)都往里塞不加以過濾或者去重可能會(huì)出現(xiàn)同一個(gè)初始時(shí)刻 x0 被多次收集。舉個(gè)例子如果數(shù)組 a 里有兩個(gè)位置顏色相同比如 a[1] a[3] c而 b 里也有對(duì)應(yīng)同色位置理論上它們會(huì)分別產(chǎn)生兩個(gè)不同的對(duì)齊時(shí)刻 x0 和 x0但如果兩個(gè)位置對(duì)最后解出來的 x0 恰好相等呢這種情況可能出現(xiàn)嗎仔細(xì)想想x0 由i mod n和j mod m唯一確定如果 x0 相等那么 i x0 mod nj x0 mod m也就是說位置對(duì)本身是唯一的。所以在真正合法的位置對(duì)里x0 不會(huì)重復(fù)。但如果你在過濾階段沒有做i % g j % g的判斷用 EXCRT 解出來可能返回同一個(gè) r 嗎其實(shí)不會(huì)因?yàn)槿绻?(i, j) 不同r 在模 L 下也不同。但為了保險(xiǎn)起見我在代碼里還是會(huì)對(duì) matchPos 做一次 sort unique畢竟不怕一萬只怕萬一多一行代碼的成本可以忽略不計(jì)。6. 這套組合還能用在哪些題上6.1 識(shí)別“周期匹配 第 k 事件”的題型特征刷題刷多了之后你會(huì)發(fā)現(xiàn)很多題都有一個(gè)共同的骨架兩個(gè)周期事件可能相同也可能不同然后問第 k 次某種狀態(tài)發(fā)生在什么時(shí)候。比如兩個(gè)交通信號(hào)燈以不同周期循環(huán)問你第 k 次同時(shí)變綠兩個(gè)機(jī)器人以不同步長走路問你第 k 次踩到同一個(gè)格子。這類問題一旦出現(xiàn)數(shù)據(jù)范圍又很大基本就能鎖定是“Chinese Remainder 二分”的組合。識(shí)別這種題型的信號(hào)有題目中出現(xiàn)兩個(gè)不同周期的循環(huán)序列查詢是第 k 次某種事件而不是請(qǐng)你輸出某個(gè)周期的狀態(tài)k 的范圍比單獨(dú)一個(gè)序列的長度大很多事件是否發(fā)生取決于兩個(gè)序列某個(gè)位置的某種關(guān)系。遇到這種題第一步永遠(yuǎn)是找公共周期 L第二步是把“事件”映射到 L 內(nèi)的有限個(gè)初始時(shí)刻第三步是二分答案。三步走完代碼基本就成型了。6.2 變體求第 k 次“匹配”而不是“不匹配”我們上面講的都是求第 k 次不和諧也就是匹配事件的反面。如果題目反過來問第 k 次匹配發(fā)生在什么時(shí)候思路完全一樣只是把判斷函數(shù)換成countMatch(T) k而已。因?yàn)槠ヅ涫录椭耙粯右彩侵芷谛缘慕y(tǒng)計(jì)函數(shù)不需要變只需要把二分和閾值條件改一下。我在寫這道題的時(shí)候一開始把 bad 函數(shù)封裝得比較死后來發(fā)現(xiàn)如果換個(gè)判斷條件又要重新寫一個(gè)邏輯。所以我在項(xiàng)目里盡量把countMatch獨(dú)立出來讓 bad 只是它的一個(gè)薄包裝。這樣不管題目問的是匹配還是不匹配核心統(tǒng)計(jì)邏輯都能復(fù)用。6.3 EXCRT 作為通用工具的獨(dú)立價(jià)值最后想單獨(dú)說一句擴(kuò)展中國剩余定理本身。它不只是這道題的一個(gè)零件在很多同余方程組相關(guān)的題目里都是核心工具。比如求某個(gè)數(shù)滿足若干個(gè)模數(shù)不互質(zhì)的余數(shù)條件或者求某些數(shù)列的最早相遇時(shí)刻都會(huì)用到這套 exgcd 合并方程的方法。我建議讀者把mergeEquation這個(gè)函數(shù)背熟它比普通 CRT 的適用范圍廣得多而且代碼量并沒有多多少。以后遇到“模數(shù)不互質(zhì)”的第一反應(yīng)就應(yīng)該是 EXCRT而不是轉(zhuǎn)過頭去試圖把數(shù)據(jù)拆成互質(zhì)的情況。我在實(shí)際編碼中還養(yǎng)成了一個(gè)習(xí)慣每次寫完 EXCRT 類型的代碼都會(huì)用一個(gè)小暴力對(duì)拍器驗(yàn)證比如隨機(jī)生成幾個(gè)同余方程手動(dòng)枚舉小范圍 x 檢查合并后的結(jié)果是否真的同時(shí)滿足所有方程。這個(gè)習(xí)慣幫我抓出了至少三次因?yàn)槿∧＿吔鐚戝e(cuò)導(dǎo)致的隱蔽 bug。雖然對(duì)拍會(huì)花幾分鐘時(shí)間但在這種數(shù)論代碼上幾分鐘的驗(yàn)證往往能省下后期幾小時(shí)的調(diào)試時(shí)間。最后再分享一點(diǎn)個(gè)人體會(huì)這道題做完之后我對(duì)“周期性事件統(tǒng)計(jì)”這類題的理解提升了一個(gè)層次。很多看似是模擬的題目核心其實(shí)都在于你能不能看穿事件的重復(fù)結(jié)構(gòu)。兩盞吊燈的循環(huán)本質(zhì)上就是兩個(gè)模數(shù) n 和 m 驅(qū)動(dòng)的狀態(tài)機(jī)整個(gè)系統(tǒng)每 lcm(n, m) 個(gè)時(shí)刻完全復(fù)刻一次。你能不能在第一個(gè)周期內(nèi)把事件的位置全部找出來能不能在第二個(gè)周期開始之后用數(shù)學(xué)方式“跳過”中間的重復(fù)決定了這道題是 O(n m) 還是 O(k) 的差距。我自己的建議是遇到這種題不要急著寫代碼先拿筆在草稿紙上列出同余方程組把合并過程和二分邊界寫清楚再動(dòng)手。數(shù)論題最怕的不是思路難而是細(xì)節(jié)多一個(gè)符號(hào)錯(cuò)位就能讓你 Debug 到懷疑人生。把 0 基時(shí)間、閉區(qū)間統(tǒng)計(jì)、先除后乘這三個(gè)習(xí)慣刻進(jìn)肌肉記憶里這類題你也能穩(wěn)定拿下。