Codeforces Edu Round 3 題目 B 解析：數學優化將 O(n²) 降為 O(n+m)

Codeforces Edu Round 3 題目 B 解析：數學優化將 O(n²) 降為 O(n+m)

題目連結：The Best Gift (CF 609B)
核心標籤：組合數學、頻率統計、複雜度優化

題目大意

書店有 n 本書（n ≤ 2×10⁵），屬於 m 種流派（m ≤ 10），每種至少一本。Jack 要買不同流派的兩本書，求方案數。兩方案若至少一本書不同則視為不同。答案不超過 2×10⁹。

暴力解法：O(n²) 超時

// 兩層迴圈檢查所有配對
for (i = 1; i < n; i++)
    for (j = 0; j < i; j++)
        if (books[i] != books[j]) ways++;
// n=2e5 時 2e10 次操作，必超時

數學洞察：補集轉換 + 頻率統計

總配對數 = C(n,2) = n(n-1)/2。
同流派配對數 = ΣC(cnt[i], 2)，其中 cnt[i] 為第 i 種流派的書本數。
不同流派配對數 = 總配對數 - 同流派配對數。

更直觀的單趟掃描累加法：

int cnt[11] = {0};
for (i = 0; i < n; i++) {
    scanf("%d", &x);
    cnt[x]++;
}
long long ans = 0;
int remaining = n;
for (i = 1; i <= m; i++) {
    remaining -= cnt[i];           // 扣除當前流派
    ans += 1LL * cnt[i] * remaining; // 當前流派 × 其後所有其他流派
}
printf("%lld\n", ans);

時間 O(n + m)，空間 O(m)，m ≤ 10 極小，瞬間 AC。

樣例驗證

核心收穫

• 組合計數轉化：直接數「滿足條件」常難，數「總數 - 不滿足條件」或「分類累加」常易
• 頻率統計：m ≤ 10 這類小範圍值，陣列計數是 O(1) 存取的最佳結構
• 長整型：n=2e5 時答案約 2e10，需 long long / __int64

此題是「暴力→數學優化」的教科書級案例，同類思想廣泛應用於配對計數、逆序對、子陣列和等問題。