雖然有在 Facebook 上面討論，遲遲沒有貼出來。由於代碼有點長，所以就放在 Github 上進行瀏覽，在此只提供文字說明，題解代碼 點我。

Problem A Magic Box

給定最多 n = 30 個數字，任意挑選至少一個數字相乘得到 P，求 P mod 1000000007 = K 的組合數有多少。

背景知識

• 中間相遇法
• 乘法反元素

藉由中間相遇法，拆成 A, B 兩堆，每一堆最多有 n/2 個數字，分別計算組合數的乘積結果的組合數 P mod 1000000007。窮舉 A 那一堆其中一個組合乘積為 PA，方法數為 CNT_PA，而為了使 PA * PB mod 1000000007 = K，利用乘法反元素，找到 PB = K * PA^-1 mod 1000000007，利用映射找到 CNT_PB，因此累計方法數就會增加 CNT_PA * CNT_PB。

特別小心 K = 0 要例外處理。

Problem B Hidden Lines

平面上給定一堆線段，請問由上而下看時，有多少被藏住的線段。

背景知識

• 分而治之
• 計算幾何
• 掃描線算法

將線段按照左端點的 x 座標值排序，接著對 x 軸座標進行分治，分治時維護區間內的天際線，合併兩個天際線的算法最慘需要 $O(n \log n)$，若不使用掃描線算法可以降到 $O(n)$，這類似合併排序，將兩個曲折的線段合併成一個。

最後遞歸 $T(n) = 2T(n/2) + O(n) = O(n \log n)$ 時間複雜度可以接受，但是代碼複雜度就很高。

Problem C Bombs

有兩種炸彈分別是單核和雙核炸彈，每一個核心都有兩個感測器，感測器又有兩種圓形、方形。若炸彈不會引爆，則至少一個核心被破壞。一個核心被破壞，則兩個感測器處於不運作。

圓形感測器不運作，則表示通過此感測器的線路都必須被剪斷。方形感測器不運作，則表示通過此感測器的線路保持正常。給予線路連接數個炸彈的感測器情況，請問是否存在一種剪斷線路的方案，滿足炸彈都不會被引爆。

背景知識

• 2-SAT

變形的 2-SAT 問題，對於每一個線段剪或不剪都是一個未知數，求方程式是否有解。對於單核炸彈而言，那個核心必須被破壞，保證通過兩個感測器的線路都必須符合不被運作的情況，一開始就指派線路剪斷或不能被剪斷。對於雙核炸彈而言，當一個核心正常，則另一個核心必然要被破壞，反之亦然，則可以 核心 A 的某條線路若正常運作導致 B 的某條線路是壞的 意即 A -> NOT B 的邏輯方程。

最後套用 2-SAT 問題進行矛盾檢查即可。

Problem D Quick Reversal

數個區間反轉操作，求奇數位數字總和

背景知識

• 模擬
• 離散處理

區間離散 + 暴力 $O(Q^2)$。區間反轉可以用 splay tree 或者是塊狀表加速，根據 SGU 187 的經驗，不會卡到 $O(Q \log Q)$

Problem E Milk Delivery

求數條 s-t 路徑恰好經過 K 條路，路上權值和最大。

背景知識

• 矩陣乘法
• 圖論

建表 $O(N^3 \log K)$，詢問 $O(1)$。