2014 ACM-ICPC 亞洲西安站區域賽題解：組合數學+容斥、GCD模擬、幾何

Problem A: Coloring (UVALive 7040)

題意：n 格子排成一行，m 種顏色，恰用 k 種顏色染色，相鄰不同色，方案數模 1e9+7。k≤1e6, n,m≤1e9。

解法：組合數 + 容斥原理 + 逆元。

1. 從 m 色選 k 色：C(m,k)。
2. 固定這 k 色，合法染色數 = 使用**恰好**這 k 色且相鄰不同的方案數。
   • 總方案（不限制用齊顏色）：k * (k-1)^(n-1)。
   • 設 A_i 為不使用第 i 種顏色的方案。由容斥：
   • Ans = Σ_{i=0}^k (-1)^i * C(k,i) * (k-i) * (k-i-1)^(n-1)。
3. 預處理階乘、逆元、快速冪，O(k log MOD) 計算。

Problem B: Easy Problem (UVALive 7035)

簽到題：輸入序列，輸出能被 3 整除的數字個數。O(n) 遍歷即可。

Problem F: Euclidean Algorithm (UVALive 7045)

題意：輸入 a,b，模擬輾轉相除法，計算商之和 + 1？實際為求某種步數統計。代碼直接遞歸 gcd 累加商。

void get(ll a, ll b) {
    if (b) { ans += a/b; get(b, a%b); }
}
// 特殊情況處理 a==b, a==0, b==0 等

總結

西安區域賽題目質量較高。Problem A 綜合考察組合數學、容斥、大數組合數計算（Lucas 定理不需要，因 k≤1e6 < MOD 可直接預處理階乘）。Problem F 是輾轉相除法的變體應用。掌握這些模板對區域賽至關重要。