Codeforces Round #167 (Div. 1) B 題解：排序與階乘計算的巧妙應用

問題背景

這是一道經典的 Codeforces 競賽題目，核心在於對數據進行排序後，利用組合數學中的階乘計算來求解答案。題目要求我們處理一系列數對 (x, y)，並根據特定規則計算排列數量，最後對給定模數取餘。

核心思路

1. 排序與分組

首先將所有數對按 x 升序排序，x 相同則按 y 升序。這使得相同 x 的元素連續分布，便於後續處理。

2. 統計相同 x 的區段長度

遍歷排序後的數組，記錄每個相同 x 區段的長度 equal_x[i]。同時檢查區段內是否存在完全相同的 (x, y) 數對，若有則計數 len_y。

3. 階乘計算與除重

答案初始為 1。對每個 x 區段長度 L，乘以 L!。但若區段內有重複的 (x, y) 數對，需除以相應的階乘進行去重。題目保證相同 (x, y) 數對最多出現兩次，因此在計算階乘時，遇到偶數項可直接除以 2，巧妙避免了模逆元的計算。

關鍵代碼片段

// 排序規則：先按 x 升序，再按 y 升序
bool cmp(node a, node b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

// 主計算邏輯
for (int i = 0; i < len_x; i++) {
    for (int j = 1; j <= equal_x[i]; j++) {
        if (len_y && (j + 1) % 2 == 0) {
            ans = (ans * (ll)((j + 1) / 2)) % m;
            len_y--;
        } else {
            ans = (ans * (ll)(j + 1)) % m;
        }
    }
}

複雜度分析

排序複雜度 O(n log n)，遍歷與計算為 O(n)，整體高效滿足題目限制。

總結

本題展示了排序分組、組合計數與模運算相結合的典型技巧。利用題目條件「重複數對最多兩次」簡化除法運算，是解題的關鍵洞察。