2021 高階競程 Contest #7 - 題解

倍倍儲蓄法

• Task Provider: D4nnyLee
• Task Setter: D4nnyLee

首殺 team21_11 (00:02)

解法說明

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

標準程式

#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;
}

玩偶工廠

• Task Provider: leo
• Task Setter: leo

首殺 team21_12 (00:20)

解法說明

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$
因此可以利用

$O(N)$ 預處理

$0!\sim {10}^5!$，
且因為

$M$ 為質數，
根據費馬小定理可以得知

$a^{M-1}\equiv 1(\text{mod}M)$
因此

$n!$ 在模

$M$ 下的反元素為

$(n!{)}^{M-2}\text{mod}M$
利用快速冪可以在

$O(N\log N)$ 的時間內得到

$0!\sim {10}^5!$ 在模

$M$ 下的反元素。
每次詢問只需套公式即可得出解答。

標準程式

#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

• Task Provider: D4nnyLee
• Task Setter: D4nnyLee

首殺 team21_11 (01:16)

解法說明

我們可以先回去參考以前的題解，
從題解中可以知道

$d{p}_{i,0}=2d{p}_{i-1,0}+2d{p}_{i-1,1}+d{p}_{n-2,0}$，
以及

$d{p}_{i,1}=d{p}_{i-1,0}+d{p}_{i-1,1}$。

這題因為

$n$ 很大所以跟之前一樣跑時間複雜度為

$O(n)$ 的方法是不會過的，
而這題需要改成使用快速冪來解題。

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

$$\left[\begin{array}{ccc}2& 2& 1\\ 1& 1& 0\\ 1& 0& 0\end{array}\right]\left[\begin{array}{c}d{p}_{i,0}\\ d{p}_{i,1}\\ d{p}_{i-1,0}\end{array}\right]=\left[\begin{array}{c}d{p}_{i+1,0}\\ d{p}_{i+1,1}\\ d{p}_{i,0}\end{array}\right]$$

也就可以得出：

$${\left[\begin{array}{ccc}2& 2& 1\\ 1& 1& 0\\ 1& 0& 0\end{array}\right]}^{n-1}\left[\begin{array}{c}d{p}_{1,0}=2\\ d{p}_{1,1}=1\\ d{p}_{0,0}=1\end{array}\right]=\left[\begin{array}{c}d{p}_{n,0}\\ d{p}_{n,1}\\ d{p}_{n-1,0}\end{array}\right]$$

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

標準程式

#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;
}

電力園區

• 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 運算速度較慢，因此較不推薦。

標準程式

#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";
}