# 2018 TOI 入營考題解
## A. 化學元素分析（Chemical Analysis）[TIOJ 2051](https://tioj.ck.tp.edu.tw/problems/2051)

括號序列的 parser，可用 [Shunting-yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm)
只需要一個 stack。

- 時間複雜度：$O(N^2 \log N)$ （應該ㄅ）
- 空間複雜度：$O(N)$ （其實我不確定？）

因為這題範圍很小所以我沒有寫複雜度更好的解（也沒有想 XD）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    stack<map<string, int>> st;
    string s;
    cin >> s;
    cout << s << endl;
    s = "(" + s + ")";
    for (int i = 0; i < s.size(); ++i) {
        if (isalpha(s[i])) {
            if (islower(s[i + 1]))
                st.push({{s.substr(i++, 2), 1}});
            else
                st.push({{s.substr(i, 1), 1}});
        } else if (isdigit(s[i])) {
            int x = 0;
            while (isdigit(s[i]))
                x = 10 * x + s[i++] - '0';
            --i;
            for (auto & p : st.top())
                p.second *= x;
        } else if (s[i] == '(') {
            st.emplace();
        } else if (s[i] == ')') {
            map<string, int> a, b;
            do {
                b = st.top();
                st.pop();
                for (auto p : b)
                    a[p.first] += p.second;
            } while (b.size());
            st.push(a);
        }
    }
    assert(st.size() == 1);
    for (auto [a, b] : st.top())
        cout << a << ":" << b << endl;
}

## B. 排列第幾個？（Permutation）[TIOJ 2052](https://tioj.ck.tp.edu.tw/problems/2052)

這是一個排列組合 / 數論問題。
$\pi$ 是該些字母排列中的第 $K$個，表示比他字典序小的排列有 $K$ 個，所以問題其實是統計比他小的排列數量。

比 $\pi$ 字典序小的排列 $\sigma$ 可以照他跟 $\pi$ 的共同前綴長度來分類，假設是 $i$ 好了，
$\sigma$ 必須滿足

- $\forall j \in [1, i], \sigma_j = \pi_j$
- $\sigma_{i+1} < \pi_{i+1}$

可以發現這樣的 $\sigma$ 數量是可以輕鬆的用可重複的排列數算出來的。
（練習：請寫出這個公式）

實做上會遇到的問題是我們需要做除法，而 $\mod D$ 時只有跟 $D$互質的數字有模反元素，怎麼辦呢？

可以利用這題的性質：每個我們要加到答案的數字都是整數。
因此所有做除法的地方必定是整除的，於是我們可以把每個數字跟 $D$共同的質因數都提出來，他們的乘除用冪次的加減即可。

換句話說，當 $D=\prod_{i=1}^{\omega(D)} {p_i}^{e_i}$ 時，對於一個數字 $n=q \prod_{i=1}^{\omega(D)} {p_i}^{e_i(n)}$，其中 $q$ 跟 $D$ 互質，我們用一個向量 $\{q, e_1(n), e_2(n), \cdots, e_{\omega(D)}(n) \}$ 來表示它。

- 時間複雜度：$O(N \Sigma \omega(D))$, $\Sigma = 52$ 是字元集大小，$\omega(D)$ 是 $D$ 的[相異質因數數量](http://mathworld.wolfram.com/DistinctPrimeFactors.html)，在這題的範圍內，$\omega(D) \le 5$。（練習：請證明這個不等式）
- 空間複雜度：$O(N \omega(D))$

#include<bits/stdc++.h>
using namespace std;
void exgcd(int a, int &x, int b, int &y, int & g)
{
    if (b) {
        exgcd(b, y, a%b, x, g);
        y -= a/b * x;
    } else {
        x = 1;
        y = 0;
        g = a;
    }
}
int minv(int a, int m)
{
    int x, y, g;
    exgcd(m, x, a, y, g);
    assert(g == 1);
    return (y % m + m) % m;
}
int qpow(int a, int b, int m)
{
    int r = 1 % m;
    for (;b;b>>=1,a=a*a%m)
        if (b&1)
            r=r*a%m;
    return r;
}
int D;
vector<int> p;
vector<int> e;
const int N = 1087;
struct mint
{
    int r;
    vector<int> q;
    mint(int a = 1)
    {
        q.assign(e.size(), 0);
        for (int i = 0; i < e.size(); ++i) {
            while (a % p[i] == 0)
                a /= p[i], ++q[i];
        }
        r = a;
    }
    mint operator * (const mint & x) const
    {
        mint ret;
        ret.r = r * x.r % D;
        for (int i = 0; i < p.size(); ++i)
            ret.q[i] = q[i] + x.q[i];
        return ret;
    }
    mint operator / (const mint & x) const
    {
        mint ret;
        ret.r = r * minv(x.r, D) % D;
        for (int i = 0; i < p.size(); ++i)
            ret.q[i] = q[i] - x.q[i];
        return ret;
    }
    int operator () (void) const
    {
        int ret = r;
        for (int i = 0; i < p.size(); ++i)
            ret = ret * qpow(p[i], q[i], D) % D;
        return ret;
    }
} w[N], iw[N];
void precalc()
{
    int ot = D;
    for (int i = 2; i * i <= ot; ++i)
        if (ot % i == 0) {
            p.push_back(i);
            e.push_back(0);
            for (; ot % i == 0; ot /= i, e.back()++);
        }
    if (ot > 1)
        p.push_back(ot), e.push_back(1);
}
string o, s;
int cnt[26*2];
int main()
{
    cin >> D >> s;
    precalc();
    for (char c = 'a'; c <= 'z'; ++c) o += c;
    for (char c = 'A'; c <= 'Z'; ++c) o += c;
    sort(begin(o), end(o));
    for (char & c : s)
        c = find(begin(o), end(o), c) - begin(o);
    int n = s.size();
    iw[0] = iw[1] = w[0] = w[1] = mint(1);
    for (int i = 2; i < N; ++i) {
        w[i] = mint(i);
        iw[i] = w[0] / w[i];
    }
    mint tot;
    assert(tot() == 1);
    int ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        int len = n - i;
        tot = tot * w[len - 1];
        tot = tot * iw[++cnt[s[i]]];
        for (int j = 0; j < s[i]; ++j) 
            if (cnt[j]) {
                (ans += (tot * w[cnt[j]])()) %= D;
                /* (len-1)! / ((cnt[k] - (k == j))! for k=0 to 51) */
            }
    }
    cout << ans << endl;
}

## C. 費氏數列（Fibonacci）[TIOJ 2053](https://tioj.ck.tp.edu.tw/problems/2053)

這是一個二階[線性遞迴](http://www.csie.ntnu.edu.tw/~u91029/Sequence2.html#2)問題，十分經典。
可以用矩陣快速冪求解。

- 時間複雜度：$O(\log N)$
- 空間複雜度：$O(1)$

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int W = 2;
typedef long long ll;
struct mat
{
    ll a[W][W];
    mat() : a{} {}
    mat operator * (const mat & rhs) const
    {
        mat ret;
        for (int k = 0; k < W; ++k)
            for (int i = 0; i < W; ++i)
                for (int j = 0; j < W; ++j)
                    (ret.a[i][j] += a[i][k] * rhs.a[k][j]) %= MOD;
        return ret;
    }
} A, V;
int main()
{
    int n;
    cin >> V.a[1][0] >> V.a[0][0] >> A.a[0][1] >> A.a[0][0] >> n;
    A.a[1][0] = 1;
    n -= 2;
    for (; n; n >>= 1, A = A * A)
        if (n & 1)
            V = A * V;
    cout << V.a[0][0] << endl;
}

## D. 最大矩形涵蓋（cover） [TIOJ 2054](https://tioj.ck.tp.edu.tw/problems/2054)

對於任意選取的一個矩形，你總是能把它往下平移直到碰到一個被蓋住的點，過程中矩形內的點只會變多或不變，不會變少。
往左平移同理。
於是你只需要考慮右上角座標是 $(a = x_i, b = y_j)$ 的那些矩形，共有 $O(N^2)$ 個。
對每個矩形你要算有幾個點被他覆蓋，這是一個矩形求和問題，可以用二維[前綴和](https://oi-wiki.org/basic/prefix-sum/)解決。
因為這題的值域很大，需要[離散化](https://oi-wiki.org/misc/discrete/)。

- 時間複雜度：$O(N^2)$
- 空間複雜度：$O(N^2)$

#include<bits/stdc++.h>
using namespace std;
const int N = 3087;
int x[N], y[N], s[N][N];
int main()
{
    int n, l, w;
    cin >> n >> l >> w;
    vector<int> vx = {-1}, vy = {-1};
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
        vx.push_back(x[i]);
        vy.push_back(y[i]);
    }
    sort(vx.begin(), vx.end());
    vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
    sort(vy.begin(), vy.end());
    vy.resize(unique(vy.begin(), vy.end()) - vy.begin());
    for (int i = 1; i <= n; ++i) {
        int a = lower_bound(vx.begin(), vx.end(), x[i]) - vx.begin();
        int b = lower_bound(vy.begin(), vy.end(), y[i]) - vy.begin();
        s[a][b]++;
    }
    int ans = 0;
    for (int i = 1, li = 0; i < vx.size(); ++i) {
        while (vx[i] - vx[li + 1] > w)
            ++li;
        for (int j = 1, lj = 0; j < vy.size(); ++j) {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            while (vy[j] - vy[lj + 1] > l)
                ++lj;
            ans = max(ans, s[i][j] - s[i][lj] - s[li][j] + s[li][lj]);
        }
    }
    cout << ans << endl;
}

## E. 直升機（Helicopter） [TIOJ 2055](https://tioj.ck.tp.edu.tw/problems/2055)

就 [RMQ 問題](https://oi-wiki.org/topic/rmq/)
$O(N \log N)$ 的作法有幾百種
可以用競賽中常用到的線段樹或 Sparse Table

很裸的線段樹題吧（？）
所以我不寫線段樹（？）
離線單調隊列 + 二分搜
有夠短(?)

- 時間複雜度：$O(N \log N)$
- 空間複雜度：$O(N)$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 87;
int n, h[N], ans[N];
vector<pair<int,int>> q[N];
deque<int> m;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        ++h[i];
    }
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        q[l].emplace_back(r, i);
    }
    for (int l = n; l >= 1; --l) {
        while (m.size() && h[m[0]] >= h[l])
            m.pop_front();
        m.push_front(l);
        for (const auto & [r, i] : q[l])
            ans[i] = h[*(upper_bound(begin(m), end(m), r) - 1)];
    }
    for (int i = 0; i < n; ++i)
        cout << ans[i] << '\n';
}