AP325 練習題解 (Ch02)

Q-2-4. 快速冪–200 位整數

快速冪是將指數拆分成 $2^k$ 次冪，例如：

3^{13} = 3^{(1101)_2} = 3^8 \cdot 3^4 \cdot 3^1

由於 1 次的平方是 2 次，2 次的平方是 4 次，依此類推，計算 n 次的複雜度只需要 $O(\log n)$ ，實作出來就是快速冪的迴圈法。

由於這題的 x 的範圍遠超過 long long，因此需要先取 x mod p 的餘數：

x = s[0] - '0';
for (int i = 1; i < s.size(); i++)
    x = (x * 10 % p + s[i] - '0') % p;

Q-2-5. 快速計算費式數列第 n 項

首先，根據費式數列定義可以得出

\begin{bmatrix} f(n) \\ f(n - 1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(n - 1) \\ f(n - 2) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n - 2} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n - 1} \begin{bmatrix} 1 \\ 0 \end{bmatrix}

可以擴展為

\begin{bmatrix} f(n + 1) & f(n) \\ f(n) & f(n - 1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n - 1} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n

接著使用 fast doubling 來簡化矩陣運算：

\begin{aligned} \begin{bmatrix} f(2n + 1) \\ f(2n) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{2n} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\ &= \begin{bmatrix} f(n + 1) & f(n) \\ f(n) & f(n - 1) \end{bmatrix}^2 \begin{bmatrix} 1 \\ 0 \end{bmatrix} \end{aligned}

得到奇數與偶數的公式分別為：

$f(2n + 1) = f(n + 1)^2 + f(n)^2$
$f(2n) = f(n)(2f(n + 1) - f(n))$

再使用快速冪的方法計算（注意回傳的值是 $f(n)$ 與 $f(n + 1)$ 組成的 pair）：

int P = 1000000007;
pair<long long, long long> fib(int n) {
    if (n == 0) return {0, 1};
    auto p = fib(n >> 1);   // p.first = f(n), p.second = f(n + 1)
    int c = (2 * p.second - p.first) % P;
    if (c < 0) c += P;
    c = (p.first * c) % P;
    int d = (p.first * p.first + p.second * p.second) % P;
    if (n & 1)
        return {d, c + d};
    else
        return {c, d};
}

由於計算平方時可能會 overflow，因此 pair 要用 long long。取餘數時可能會出現 $f(n) < P, f(n + 1) > P$ 的情況，導致 c 變成負數，因此要將 $f(n)$ 的公式拆成兩部分額外判斷負數。

Q-2-7. 互補團隊

這題可以使用與 P-1-7. 子集合乘積相同的方法，第 i 個 bit 為 1 表示包含第 i 個字母：

int k = (1 << m) - 1;  // bits 0 ~ (m - 1) are 1
for (int i = 0; i < n; i++) {
    cin >> s;
    int team = 0, len = s.size();
    for (int j = 0; j < len; j++)
        team |= 1 << (s[j] - 'A');
    a[i] = team;
}

然後將陣列 sort 後，使用雙指針分別從前後往中間檢查，當兩數相加等於 k 表示互補，當後指針大於前指針即可結束遍歷。

int i = 0, j = n - 1;
for (; i < n; i++) {
    while (j > i && a[j] > k - a[i]) j--;
    if (a[i] + a[j] == k) cnt++;
}

Q-2-8. 模逆元

由於除法不像加、減、乘一樣，可以對每個數取模而不影響結果，例如 (3 * 6 / 3) % 7 不等於 (3 % 7) * (6 % 7) / (3 % 7)，這樣在運算過程可能超過 long long 時會造成困擾。我們可以用模逆元來將除法轉換為乘法來解決這個問題。

模逆元又稱為模反元素，也就是在模運算下的乘法反元素，若 $ax\equiv 1{\pmod{b}}$ ，則 $a, x$ 互為模 $b$ 的模逆元，同時也可寫成 $x\equiv \cfrac{1}{a}{\pmod{b}}$ 。

套用到剛剛的例子，3 mod 7 的模逆元為 5，因此可以把式子變為 (3 % 7) * (6 % 7) * (5 % 7)，得到的答案是一樣的。

除了最直覺的窮舉法以外，有兩個主要方法可以求模逆元：

擴展歐幾里得算法

歐幾里得算法，也就是我們熟悉的輾轉相除法，用來求得 $a, b$ 兩數的最大公因數。擴展歐幾里得算法則是在求出最大公因數的同時，找出符合以下等式（貝祖等式）的 $x, y$ ：

ax + by = \gcd(a, b)

從歐幾里得算法可以得知 $\gcd(a, b) = \gcd(b, a\bmod b)$ ，又 $a\bmod b = a - kb, k = \lfloor a / b\rfloor$ 。因此可以對上面的等式進行處理：

\begin{aligned} ax + by &= \gcd(a, b) \\ &= \gcd(b, a\bmod b) \\ &= \gcd(b, a - kb) \\ &= bx' + (a - kb)y' \\ &= ay' + b(x' - ky') \end{aligned}

可以用 $x = y', y = x' - ky'$ 來遞迴求解，當 $b = 0$ 時終止，此時 $x = 1, y = 0$ 。

回到模逆元的公式， $ax\equiv 1{\pmod{b}}$ 等於 $ax - kb = 1$ ，設 $-k = y$ 得到 $ax + by = 1$ ，求出 $x$ 即為 $a$ 的模逆元：

void exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

由於使用擴展歐幾里得求出的解有可能是負數，此時需要再加上 $b$ 使其變為正數。

此方法的複雜度是 $O(\log(\min(a, b)))$ ，只要模逆元存在（也就是 $a, b$ 互質）就能使用，是最穩定的方法，費法小定理則限定 $b$ 必須為質數。

費馬小定理

根據費馬小定理，若 $a$ 為整數， $p$ 為質數，則

a^{p-1}\equiv 1{\pmod p}

將一個 $a$ 提出後可以得到

a\cdot a^{p-2}\equiv 1{\pmod p}

因此我們可以直接用快速冪求出 $a^{p-2}\pmod p$ 即為 $a$ 的模逆元。

Q-2-10. 子集合的和(折半枚舉)

首先將輸入的陣列拆成兩半，用遞迴分別枚舉小於 p 的和並存入 s1, s2 兩個 set，接著遍歷 s1，尋找小於 p 的最大值：

for (LL e : s1) {
    tmp = e + *(prev(s2.lower_bound(p - e)));
    if (tmp > MAX) MAX = tmp;
}

由於 set 的資料是有序的，這裡使用 s1.lower_bound() 來求出大於或等於 p - e 的最小值的位置，此函式回傳的是雙向迭代器，因此我們可以用 prev() 來取得前一個位置，也就是小於 p - e 的最大值的位置，再用 * 取值。

若使用 s1.lower_bound() 搜尋的值超過集合的最大值會回傳 s1.end()，使用 prev() 取到的值就會是此集合的最大值。

Q-2-12. 最接近的子矩陣和（未解決）

這題跟例題一樣使用前綴和 + set 來解時複雜度為 $O(m^2 n\log{n})$ ，但離 1s 的時間限制還有很大的差距，若之後找到更好的方法會在此處補上。

Q-2-13. 無理數的快速冪

假設給定的無理數是 $a + b\sqrt{2}$ ，與另一無理數 $x + y\sqrt{2}$ 相乘的結果為

(a + b\sqrt{2})(x + y\sqrt{2}) = (ax + 2by) + (ay + bx)\sqrt{2}

若是自身的平方則為

(a + b\sqrt{2})^2 = (a^2 + 2b^2) + 2ab\sqrt{2}

將上述結果套入前綴和的函式即可。

Q-2-14. 水槽

這題可以使用遞迴，根據不同情況來計算水量並逐漸縮減區間。

首先將所有擋板高度與其編號以 pair<long long, int> 的形式存在陣列裡，再由高到低排序。運算過程可能會超過 int 上限，所以使用 long long 儲存擋板高度。

進入遞迴時，先找出區間內最高的擋板（開區間，不包含左邊界和右邊界）。由於會逐漸縮減區間，每次找到的最高擋板都會被排除，我們可以用一個全域變數儲存當前區間最高擋板的 index，之後只要往後單向搜尋即可。

計算時需要考慮以下四種情況：

區間內只有一個水槽，則水位等於剩餘水量，return。
若剩餘水量大於等於 區間內水槽數 x 最高擋板高度，表示足以淹沒整個區間，則區間內水位均為平均值，return。
若無法淹沒整個區間，則以最高擋板為準分成兩邊，若水量不足以淹沒包含注入點的這一邊（不會溢出到另一邊），則將縮小區間再次遞迴。
若水量能淹沒包含包含注入點的區間，則這一邊的水位皆為最高擋板的高度，則求出剩餘水量後縮減區間，並更改注入點為緊鄰最高擋板的水槽。

整個遞迴函式皆操作同一個陣列，計算結束後直接輸出即可。##

P-2-15. 圓環出口

講義中提到可以將儲存房間點數的 p[] 變成前綴和的形式，此時 p[] 為單調（遞增或遞減）陣列，可以用二分搜來搜尋。

我們可以在輸入 q 的同時進行計算。首先建立一個變數 room 表示當前在哪個房間，若不在第 0 個房間，則將 q 加上前綴和 p[room - 1]，補足前面房間的分數。如果加完後 q > p[n - 1] 表示途中會回到第 0 個房間，將 q 減去 p[n - 1] 並將 room 設為 0。最後用 lower_bound() 搜尋後進到下一個房間（注意超過第 n 個房間要回到 0）。