---
tags: 成大高階競技程式設計 2021
image: https://i.imgur.com/IIj9BcL.png
---

# 2021 高階競程 Contest #7 - 題解

## [倍倍儲蓄法](https://judge.csie.ncku.edu.tw/problems/127)
- Task Provider: D4nnyLee
- Task Setter: D4nnyLee

### 首殺 team21_11 (00:02)

### 解法說明

這題用暴力破解就可以 AC。

### 標準程式
:::spoiler

#include <iostream>
using namespace std;

constexpr int mod{1000000007};

void test_case() {
    int n;
    cin >> n;

    int ans = 1;
    for (int i{1}; i < n; ++i)
        ans = (ans * 2) % mod;

    cout << ans << '\n';
}

int main() {
    int q;
    cin >> q;
    while (q--)
        test_case();

    return 0;
}

:::

## [玩偶工廠](https://judge.csie.ncku.edu.tw/problems/128)
- Task Provider: leo
- Task Setter: leo

### 首殺 team21_12 (00:20)

### 解法說明

$\tbinom{n}{k}=\frac{n!}{k!(n-k)!}$
因此可以利用 $O(N)$ 預處理 $0!\sim10^5!$，
且因為 $M$ 為質數，
根據費馬小定理可以得知 $a^{M-1}\equiv1\ (\text{mod}\ M)$
因此 $n!$ 在模 $M$ 下的反元素為 $(n!)^{M-2}\ \text{mod}\ M$
利用快速冪可以在 $O(N\log N)$ 的時間內得到 $0!~\sim10^5!$ 在模 $M$ 下的反元素。
每次詢問只需套公式即可得出解答。

### 標準程式
:::spoiler

#include <iostream>
using namespace std;

long long fact[100001] = {1}, rev[100001] = {1}, MOD;

inline long long power(long long a, long long b){
    long long ans = 1;
    while(b){
        if(b & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

inline long long C(int n, int k){
    return fact[n] * rev[k] % MOD * rev[n - k] % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t, n, k;
    cin >> t >> MOD;
    for(int i = 1; i <= 100000; i++){
        fact[i] = fact[i - 1] * i % MOD;
        rev[i] = power(fact[i], MOD - 2);
    }
    while(t--){
        cin >> n >> k;
        cout << C(n, k) << "\n";
    }
}

:::

## [收納的智慧。Extreme](https://judge.csie.ncku.edu.tw/problems/129)
- Task Provider: D4nnyLee
- Task Setter: D4nnyLee

### 首殺 team21_11 (01:16)

### 解法說明

我們可以先回去參考[以前的題解](https://hackmd.io/@nckuacm/ryF3RbxvY#%E6%94%B6%E7%B4%8D%E7%9A%84%E6%99%BA%E6%85%A7%E3%80%82Hard)，
從題解中可以知道 $dp_{i, 0} = 2 dp_{i - 1, 0} + 2 dp_{i - 1, 1} + dp_{n - 2, 0}$，
以及 $dp_{i, 1} = dp_{i - 1, 0} + dp_{i - 1, 1}$。

這題因為 $n$ 很大所以跟之前一樣跑時間複雜度為 $O(n)$ 的方法是不會過的，
而這題需要改成使用快速冪來解題。

從上面的兩個等式我們可以再寫出以下等式：

$$
\left[
\begin{matrix}
2 & 2 & 1 \\
1 & 1 & 0 \\
1 & 0 & 0
\end{matrix}
\right]
\left[
\begin{matrix}
dp_{i, 0} \\
dp_{i, 1} \\
dp_{i - 1, 0}
\end{matrix}
\right] =
\left[
\begin{matrix}
dp_{i + 1, 0} \\
dp_{i + 1, 1} \\
dp_{i, 0}
\end{matrix}
\right]
$$

也就可以得出：

$$
\left[
\begin{matrix}
2 & 2 & 1 \\
1 & 1 & 0 \\
1 & 0 & 0
\end{matrix}
\right]^{n - 1}
\left[
\begin{matrix}
dp_{1, 0} = 2 \\
dp_{1, 1} = 1\\
dp_{0, 0} = 1
\end{matrix}
\right] =
\left[
\begin{matrix}
dp_{n, 0} \\
dp_{n, 1} \\
dp_{n - 1, 0}
\end{matrix}
\right]
$$

$dp_{n, 0}$ 就是我們最後要的答案。

### 標準程式
:::spoiler

#include <iostream>
#include <vector>
#include <array>

using namespace std;

constexpr int mod{1000000007};

void mul(array<array<long long, 3>, 3> a,
         array<array<long long, 3>, 3> b,
         array<array<long long, 3>, 3> &ret) {
    for (int i{0}; i < 3; ++i)
        for (int j{0}; j < 3; ++j) {
            ret[i][j] = 0;
            for (int k{0}; k < 3; ++k) {
                ret[i][j] += a[i][k] * b[k][j] % mod;
                ret[i][j] %= mod;
            }
        }
}

int main() {
    long long n;
    cin >> n;

    --n;

    array<array<long long, 3>, 3> A{2, 2, 1, 1, 1, 0, 1, 0, 0}, ans{1, 0, 0, 0, 1, 0, 0, 0, 1};
    for (; n; n >>= 1) {
        if (n & 1)
            mul(ans, A, ans);
        mul(A, A, A);
    }

    cout << (2 * ans[0][0] % mod + ans[0][1] + ans[0][2]) % mod << '\n';

    return 0;
}

:::

## [電力園區](https://judge.csie.ncku.edu.tw/problems/130)
- Task Provider: leo
- Task Setter: leo

### 首殺 team21_34 (01:12)

### 解法說明

因為是覆蓋所有點且周長最短的多邊形，
可以得知要求的是凸包的面積，
因此只要先求出凸包，
再利用 cross 計算有向面積加總，
cross 得出來的面積是平行四邊形的面積，
因此需要除以 $2$ 才是正確的面積。

因為 double 精度不足的原因，
可以先將所有 cross 得到的有向面積加起來，
最後再除以 $2$，小數點後的數字只會有 $.0$ 或 $.5$，
直接以奇偶數特判輸出即可。

另一個方法是用 long double，
因為 long double 精度有 18 位。
但是 long double 運算速度較慢，因此較不推薦。

### 標準程式
:::spoiler

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Point{
    long long x, y;
    Point(long long x = 0, long long y = 0) : x(x), y(y){}
    Point operator-(const Point &b)const{
        return Point(x - b.x, y - b.y);
    }
    long long cross(const Point &b)const{
        return x * b.y - y * b.x;
    }
};

bool cmp(const Point &a, const Point &b){
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}

vector<Point> convexHull(vector<Point> v){
    int sz = 0;
    vector<Point> ans;
    sort(v.begin(), v.end(), cmp);
    for(size_t i = 0; i < v.size(); i++){
        while(sz >= 2 && (ans[sz - 1] - ans[sz - 2]).cross(v[i] - ans[sz - 2]) <= 0)
            ans.pop_back(), sz--;
        ans.push_back(v[i]), sz++;
    }
    for(int i = int(v.size()) - 2, t = sz + 1; i >= 0; i--){
        while(sz >= t && (ans[sz - 1] - ans[sz - 2]).cross(v[i] - ans[sz - 2]) <= 0)
            ans.pop_back(), sz--;
        ans.push_back(v[i]), sz++;
    }
    if(v.size() > 1)
        ans.pop_back();
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n, x, y, ans = 0;
    vector<Point> v, convex;
    cin >> n;
    while(n--){
        cin >> x >> y;
        v.push_back(Point(x, y));
    }
    convex = convexHull(v);
    for(int i = 0; i < convex.size(); i++)
        ans += convex[i].cross(convex[(i + 1) % convex.size()]);
    cout << (ans >> 1) << (ans & 1 ? ".5" : ".0") << "\n";
}

:::