# 112 學年度建中資訊校內第一次模擬賽 題解

## [pA. 老鼠與貓咪](https://tioj.ck.tp.edu.tw/problems/2325)

Setter：becaido

### Subtask 1：$n,q\le 3000$

題目可以簡化成 $x=a_0$，每次 $x=|x-a_i|$，問最後 $x$ 是多少。

暴力做是 $O(nq)$ 的。

### Subtask 2：$a_i\le a_{i+1}$（$0\le i<n$）

發現每次 $x\leq a_i$，所以 $x$ 會變成 $a_i-x$，答案會是 $a_i$ 一正一負相加的總和。

例如當 $p=5$，答案會等於 $a_5-(a_4-(a_3-(a_2-(a_1-a_0))))=a_5-a_4+a_3-a_2+a_1-a_0$。

可以用前綴和 $O(1)$ 算，複雜度 $O(n+q)$。

### Subtask 3：無其他限制

$a_0$ 會是 $0\sim 10^6$ 的其中一個，可以把這些數字變成一個區間，丟到數線上，離線更新與處理查詢。

每次與一個 $a_i$ 做運算時，根據這個區間在原點右邊或原點左邊，可以知道它要往左移還是往右移 $a_i$ 格，可能會有區間不跨越原點與跨越原點兩種情況。

對於跨越原點這種情況，整段區間會是原點左邊與原點右邊的區間所組成的，利用並查集可以把小的那一段 merge 到大的那一段。


時間複雜度可以到 $O(n+C\alpha(C)+q)$，$C$ 為值域，空間複雜度 $O(n+C+q)$。

:::spoiler code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
const int MAX = 1e6;

int n, q;
int a[N], ans[N];
vector<pair<int, int>> ask[N];

int L, R, l, r;
int to[MAX + 5];
int dsu(int x) {
    return x == to[x] ? x : (to[x] = dsu(to[x]));
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= q; i++) {
        int x, p;
        cin >> x >> p;
        ask[p].emplace_back(x, i);
    }
    iota(to, to + MAX + 1, 0);
    R = r = MAX;
    for (int i = 1; i <= n; i++) {
        if (l >= 0) l -= a[i], r -= a[i];
        else l += a[i], r += a[i];
        if (l < 0 && r > 0) {
            if (-l <= r) {
                for (int j = l; j < 0; j++) to[j + (L - l)] = -j + (L - l);
                L -= l, l = 0;
            } else {
                for (int j = 1; j <= r; j++) to[j + (R - r)] = -j + (R - r);
                R -= r, r = 0;
            }
        }
        for (auto [x, id] : ask[i]) {
            x = dsu(x);
            ans[id] = x + (l - L);
        }
    }
    for (int i = 1; i <= q; i++) cout << abs(ans[i]) << '\n';
}

:::

:::spoiler Bonus
[luogu P8264](https://www.luogu.com.cn/problem/P8264)
:::

## [pB. 送外賣](https://tioj.ck.tp.edu.tw/problems/2324)

Setter：becaido

[題目出處](https://atcoder.jp/contests/cf17-final/tasks/cf17_final_j)

### Subtask 1：$n\leq 1000$

題目在問的是最小生成樹邊權和。

可以以每個人為根，暴力找出所有邊，之後排序完用 Kruskal，複雜度 $O(n^2\log n)$。

也可以利用[運送蛋餅](https://tioj.ck.tp.edu.tw/problems/2164)的想法，用 Prim 做到 $O(n^2)$。

### Subtask 2：$u_i=1,v_i=i+1$

樹是一個星狀圖，令 $w_1=0,w_i$ 是 $i$ 與 $1$ 的邊權，令 $A_i=a_i+w_i$。

$W(i,j)=D(i,j)+a_i+a_j=A_i+A_j$，選擇 $A_i$ 最小的那個人，與其他 $n-1$ 個人相連即是最小生成樹。

複雜度 $O(n)$。

### Subtask 3：$u_i=i,v_i=i+1$

樹會是一條鏈。

有兩種做法：

做法一：把所有可能在最小生成樹上的邊加進來，排序後用 Kruskal。

利用分治的想法，每次把鏈切成左右兩邊，令 $A_i=a_i+w'_i$，$w'_i$ 是 $i$ 離中心點的距離。

左右兩邊各選一點 $i_l,i_r$，相連的邊權是 $A_{i_l}+A_{i_r}$，會發現選 $A_i$ 最小的那個人跟另外一個區間的所有人相連會是最好的，如果不小心跟自己這個區間的人連邊也沒關係，因為在此時的邊權會比實際的大，排序後在前面的邊權比較小，會比自己早連。

處理完一個大區間可以遞迴左右兩個區間，總共會有 $O(n\log n)$ 條邊。
時間複雜度 $O(n\log^2 n)$，空間複雜度 $O(n\log n)$。

做法二：Borůvka's 演算法

Borůvka's 演算法的想法：剛開始會有 $n$ 個連通塊，每一輪每個連通塊選擇連出去其他連通塊最小的那條邊，之後把有連邊的連通塊 merge 起來。一直做這個動作，直到連通塊數量等於一，此時連的 $n-1$ 條邊即為最小生成樹。

每一輪連通塊數量至少減半，做 $O(\log n)$ 輪會結束。

把鏈上的每個人剛開始都視為一個連通塊，在每一輪，要維護的是每個人連向非自己連通塊的最小邊權，可以維護最小值與次小值求得，每輪 $O(n)$，時間複雜度 $O(n\log n)$，空間複雜度 $O(n)$。

### Subtask 4：無其他限制

一樣有兩個做法。

做法一：重心剖分，令 $A_i=a_i+w'_i$，$w'_i$ 為 $i$ 至重心的距離。

每次只要加入 $A_i$ 最小的與這層其他人連的邊，之後拔掉重心遞迴。

最後所有邊排序一次，做一次 Kruskal 即可。時間複雜度 $O(n\log^2 n)$，空間複雜度 $O(n\log n)$。

做法二：一樣是 Borůvka，每一輪做換根 DP，一樣維護最小值與次小值。時間複雜度 $O(n\log n)$，空間複雜度 $O(n)$。

:::spoiler code (重剖)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 2e5 + 5;

int n;
ll ans;
int a[N];
vector<pair<int, int>> adj[N];
vector<tuple<ll, int, int>> e;

bool vs[N];
int id, tag[N];
void divide(int pos) {
    int sz = 0, cent = 0;
    {
        queue<int> q;
        q.push(pos), tag[pos] = ++id;
        while (q.size()) {
            int pos = q.front();
            q.pop();
            sz++;
            for (auto [np, w] : adj[pos]) if (vs[np] == 0 && tag[np] != id) {
                q.push(np);
                tag[np] = id;
            }
        }
        auto dfs = [&](auto dfs, int pos, int fa)->int {
            int cnt = 1, mx = 0;
            for (auto [np, w] : adj[pos]) if (vs[np] == 0 && np != fa) {
                int sub = dfs(dfs, np, pos);
                cnt += sub;
                mx = max(mx, sub);
            }
            mx = max(mx, sz - cnt);
            if (mx <= sz / 2) cent = pos;
            return cnt;
        };
        dfs(dfs, pos, pos);
        vs[cent] = 1;
    }

    ll mn = LLONG_MAX, p = 0;
    queue<pair<int, ll>> q;
    q.emplace(cent, 0), tag[cent] = ++id;
    while (q.size()) {
        auto [pos, sum] = q.front();
        q.pop();
        if (a[pos] + sum < mn) {
            mn = a[pos] + sum;
            p = pos;
        }
        for (auto [np, w] : adj[pos]) if (vs[np] == 0 && tag[np] != id) {
            q.emplace(np, sum + w);
            tag[np] = id;
        }
    }
    q.emplace(cent, 0), tag[cent] = ++id;
    while (q.size()) {
        auto [pos, sum] = q.front();
        q.pop();
        e.emplace_back(a[pos] + sum + mn, pos, p);
        for (auto [np, w] : adj[pos]) if (vs[np] == 0 && tag[np] != id) {
            q.emplace(np, sum + w);
            tag[np] = id;
        }
    }

    for (auto [np, w] : adj[cent]) if (vs[np] == 0) divide(np);
}

int to[N], h[N];
int dsu(int x) {
    return x == to[x] ? x : (to[x] = dsu(to[x]));
}
bool merge(int a, int b) {
    a = dsu(a), b = dsu(b);
    if (a == b) return 0;
    if (h[a] < h[b]) swap(a, b);
    to[b] = a;
    h[a] += (h[a] == h[b]);
    return 1;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
    }
    divide(1);
    sort(e.begin(), e.end());
    iota(to + 1, to + n + 1, 1);
    for (auto [w, i, j] : e) if (merge(i, j)) ans += w;
    cout << ans << '\n';
}

:::

:::spoiler Bonus
[luogu P6199](https://www.luogu.com.cn/problem/P6199)
:::

## [pC. 偶像選拔祭](https://tioj.ck.tp.edu.tw/problems/2328)

Setter：becaido

### Subtask 1：$P=0$

沒有成本的話每個人可以自己組成一個團體。

答案為 $\sum\limits_{i=1}^N a_i$ 複雜度 $O(N)$。

### Subtask 2：$N\leq 500$

令 $dp_i$ 是前 $i$ 個人所有分法中最大的總收益，$S(l,r)$ 是 $l\sim r$ 的人前 $\min(K,r-l+1)$ 小的 $a_i$ 總和。

可以列出 DP 式：$dp_i=\max\limits_{0\le j<i}(dp_j+S(j+1,i)-P)$。
$S(j+1,i)$ 如果每次都排序求前 $\min(K,i-j)$ 小的人，複雜度為 $O(N^3\log N)$。

如果改用 nth_element 可以進一步壓到 $O(N^3)$。

### Subtask 3：$N\leq 2000$

由右往左枚舉 $j$，用一個 priority_queue 維護前 $\min(K,i-j)$ 小的人。

如果 pq 的大小超過 $K$ 了，那就把頂端的元素 pop 掉。

複雜度 $O(N^2\log N)$。

### Subtask 4：$a_i\leq a_{i+1}$（$1\leq i<N$）

先把整個陣列反轉，變成遞減的，比較好解說。

分出 $[1,K],[K+1,2K],\dots,[(i-1)K+1,iK],\dots,[\lfloor\frac{N}{K}\rfloor K+1,N]$ 的區間，每次計算答案，計算完後把最後面兩個區間合併，繼續計算答案。

可以證明每種取法都是在固定區間數量時最好的取法。

複雜度 $O(N)$。

### Subtask 5：$K=1$

回到 DP，會發現說這個 DP 滿足凹四邊形的條件，當 $i_1<i_2$，轉移到 $j$ 時 $i_1$ 比 $i_2$ 好，那在 $j$ 之後的所有人也一定是從 $i_1$ 轉移比較好，因為 $\min\limits_{i_1<i\leq j+1}a_i-\min\limits_{i_1<i\leq j}a_i\leq \min\limits_{i_2<i\leq j+1}a_i-\min\limits_{i_2<i\leq j}a_i$，最小值的遞減量一定是 $i_2$ 的比較大(或相同)，所以當某個時刻 $i_1$ 比 $i_2$ 好，那 $i_2$ 在之後一定不會優於 $i_1$ 了。

利用 stack 維護轉移點與轉移區間，做凹四邊形優化，如果用線段樹算區間最小值時間複雜度 $O(n\log^2 n)$、空間複雜度 $O(n)$；用稀疏表時間、空間複雜度 $O(n\log n)$。

### Subtask 6：無其他限制

只有 $j-i_1,j-i_2\geq K$ 的部分滿足凹四邊形。

$j-i<K$ 的部分可以用前綴和與單調隊列做，$j-i\geq K$ 的部分可以在處理 $i$ 轉移到的範圍時順便看此時誰會轉移到 $i+K$，然後把 $i+K$ 從 stack 裡移除。

區間前 $K$ 小的總和可以用持久化線段樹做。

時間複雜度 $O(N\log^2 N)$，空間複雜度 $O(N\log N)$。

:::spoiler code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 2e5 + 5;
const int H = __lg(N) + 1;

int n, k;
ll P, pre[N], dp[N];
int a[N], id[N], p[N];

struct Node {
    int cnt;
    ll sum;
    int ls, rs;
} node[4 * H * N];

int sz, root[N];
void upd(int &pos, int l, int r, int p) {
    node[++sz] = node[pos];
    pos = sz;
    if (l == r) {
        node[pos].cnt++;
        node[pos].sum += a[id[p]];
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) upd(node[pos].ls, l, mid, p);
    else upd(node[pos].rs, mid + 1, r, p);
    node[pos].cnt = node[node[pos].ls].cnt + node[node[pos].rs].cnt;
    node[pos].sum = node[node[pos].ls].sum + node[node[pos].rs].sum;
}
ll que(int pl, int pr, int l, int r, int k) {
    if (l == r) return node[pr].sum - node[pl].sum;
    int mid = (l + r) / 2;
    int lcnt = node[node[pr].ls].cnt - node[node[pl].ls].cnt;
    ll lsum = node[node[pr].ls].sum - node[node[pl].ls].sum;
    if (lcnt >= k) return que(node[pl].ls, node[pr].ls, l, mid, k);
    else return lsum + que(node[pl].rs, node[pr].rs, mid + 1, r, k - lcnt);
}
ll cal(int l, int i) {
    if (i - l <= k) return dp[l] + pre[i] - pre[l] - P;
    return dp[l] + que(root[l], root[i], 1, n, k) - P;
}

struct seg {
    int p, l, r;
    seg() {}
    seg(int p, int l, int r) : p(p), l(l), r(r) {}
};

deque<pair<int, ll>> dq;
vector<seg> st;
int from[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> k >> P;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
    iota(id + 1, id + n + 1, 1);
    sort(id + 1, id + n + 1, [&](int l, int r) {
        return a[l] < a[r];
    });
    for (int i = 1; i <= n; i++) p[id[i]] = i;
    for (int i = 1; i <= n; i++) {
        root[i] = root[i - 1];
        upd(root[i], 1, n, p[i]);
    }

    dq.emplace_back(0, 0);
    st.emplace_back(seg(0, k, n));
    for (int i = 1; i <= n; i++) {
        dp[i] = cal(from[i], i);
        if (dq.front().first + k < i) dq.pop_front();
        dp[i] = max(dp[i], dq.front().second + pre[i] - P);
        while (dq.size() && dq.back().second <= dp[i] - pre[i]) dq.pop_back();
        dq.emplace_back(i, dp[i] - pre[i]);
        if (i + k > n) continue;
        from[i + k] = st.back().p;
        st.back().l = max(st.back().l, i + k + 1);
        if (st.back().l > st.back().r) st.pop_back();
        while (st.size() && cal(i, st.back().r) >= cal(st.back().p, st.back().r)) st.pop_back();
        if (st.size() == 0) st.emplace_back(seg(i, i + k + 1, n));
        else {
            auto [p, l, r] = st.back();
            while (l < r) {
                int mid = (l + r) / 2;
                if (cal(p, mid) > cal(i, mid)) r = mid;
                else l = mid + 1;
            }
            st.back().l = l;
            if (i + k + 1 <= l - 1) st.emplace_back(seg(i, i + k + 1, l - 1));
        }
    }
    cout << dp[n] << '\n';
}

:::

:::spoiler Bonus
現在沒有出道成本 $P$ 了，但是節目限制要剛好有 $M(1\leq M\leq N)$ 個團體，請問總收益最大是多少呢？
:::

## [pD. 轉生到異世界的我，竟然變成了農夫約翰的牛 ?!](https://tioj.ck.tp.edu.tw/problems/2323)

Idea：PCC
Setter：becaido

### Subtask 1：$n,q\leq 3000$

每次詢問暴力算總和，複雜度 $O(nq)$。

### Subtask 2：只會有 $2\ p$ 的操作

可以利用單調隊列維護每個人能看到的左界與右界，詢問時用前綴和 $O(1)$ 算，複雜度 $O(n+q)$。

### Subtask 3：$h_i<h_{i+1}$（$1\leq i<n$）

每個人能看到的範圍是 $[1,i]$，可以用 BIT 或線段樹維護區間和，複雜度 $O(n+q\log n)$。

### Subtask 4：無其他限制

先用單調隊列求出每個人的範圍，然後用 BIT 或線段樹維護區間和，複雜度 $O(n+q\log n)$。

:::spoiler code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 2e5 + 5;

int n, q;
int h[N], w[N];
int L[N], R[N];

ll bit[N];
void upd(int pos, int x) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += x;
}
ll que(int pos) {
    ll re = 0;
    for (; pos; pos -= pos & -pos) re += bit[pos];
    return re;
}
ll que(int l, int r) {
    return que(r) - que(l - 1);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i];

    vector<int> st;
    for (int i = 1; i <= n; i++) {
        while (st.size() && h[i] >= h[st.back()]) st.pop_back();
        L[i] = (st.size() ? st.back() : 0) + 1;
        st.emplace_back(i);
    }
    st.clear();
    for (int i = n; i >= 1; i--) {
        while (st.size() && h[i] >= h[st.back()]) st.pop_back();
        R[i] = (st.size() ? st.back() : n + 1) - 1;
        st.emplace_back(i);
    }
    for (int i = 1; i <= n; i++) upd(i, w[i]);

    while (q--) {
        int ty, p, x;
        cin >> ty >> p;
        if (ty == 1) {
            cin >> x;
            upd(p, x - w[p]);
            w[p] = x;
        } else {
            cout << que(L[p], R[p]) << '\n';
        }
    }
}

:::

:::spoiler Bonus
$h_i$ 也有可能被修改，你能順利求出區間和嗎？
:::

## [pE. 博士愛序列](https://tioj.ck.tp.edu.tw/problems/2326)

Setter：becaido

### Subtask 1：$N,Q\leq 500$

每次詢問 $O(N^2)$ 檢查整個區間，複雜度 $O(N^2Q)$。

### Subtask 2：$N\leq 3000$

對所有 $l$ 存 $r$ 跟詢問編號，然後離線處理。

由右往左加入元素，可以 $O(n)$ 更新每個人與左邊幾個人滿足條件，利用前綴和可以 $O(1)$ 回答詢問。

複雜度 $O(N^2+Q)$。

### Subtask 3：$a_i<32$

可以利用前綴和計算詢問的區間內 $0\sim 31$ 分別有幾個，然後花 $O(32^2)$ 次去檢查。

複雜度 $O(NC + QC^2)$。

### Subtask 4：$l=1$

可離線處理詢問，由左往右加入元素，每次加入一個元素，有兩種更新方式：

一個是用 $\text{cnt}_i$ 記錄之前 $i$ 出現過了幾次，然後對加入的人 $O(C)$ 去檢查。

一個是用 $\text{cnt}_i$ 記錄新加入的人如果是 $i$ 答案會加多少，然後花 $O(C)$ 更新 $\text{cnt}$。

複雜度 $O(NC+Q)$。

### Subtask 5：無其他限制

可以用莫隊的想法，但是每次加入 / 刪除元素都要花 $O(C)$ 算太久了，想要平衡更新與查詢的複雜度。

假設現在莫隊的指針在 $[L,R]$，想要把 $R$ 右移到 $R'$，把加入的元素跟影響到的區間用數對表示可以寫成 $(R+1,[L,R]),(R+2,[L,R+1]),\dots,(R'-1,[L,R'-2]),(R',[L,R'-1])$。

會發現每個人影響到的區間左界都是 $L$，右界都是自己 $-1$，並且 $[L,R]$ 這個區間可以寫成 $[1,R]-[1,L-1]$ 的形式，於是可以把每個人影響到的區間拆成兩個左界是 $1$ 的區間，第一個的右界是自己 $-1$，可以統一算後用前綴和直接求，第二個的右界則是 $L-1$，那可以在 $L-1$ push 進 $[R+1,R']$ 這個區間，等到所有詢問都 push 完後統一求。

對於 $R$ 往左，$L$ 往左、往右的情況也是類似的，只需要微調 push 的位置與正負號。

在統一算的時候只有 $N$ 個元素要更新，所以可以花 $O(C)$ 更新，這樣詢問就只要 $O(1)$。

等到所有詢問都有結果了，因為我們算的是變化量，所以要對詢問做一次前綴和。

時間複雜度 $O(N\sqrt{Q}+NC)$。

這種方法稱為莫隊二次離線。

:::spoiler code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e5 + 5;
const int MAX = 2048;
const int Block = sqrt(N);

int n, q;
int A, B, K;
ll ans[N];
int a[N];
tuple<int, int, int> ask[N];

int cnt[MAX];
ll pre1[N], pre2[N];
vector<tuple<int, int, int, int>> op[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> q;
    cin >> A >> B >> K;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= q; i++) {
        auto &[l, r, id] = ask[i];
        cin >> l >> r;
        id = i;
    }
    sort(ask + 1, ask + q + 1, [&](auto lhs, auto rhs) {
        return get<0>(lhs) / Block != get<0>(rhs) / Block ? get<0>(lhs) < get<0>(rhs) : get<1>(lhs) < get<1>(rhs);
    });
    for (int i = 1, L = 1, R = 0; i <= q; i++) {
        auto [l, r, id] = ask[i];
        if (R < r) op[L - 1].emplace_back(R + 1, r, id, -1), R = r;
        if (L > l) op[R].emplace_back(l, L - 1, id, 1), L = l;
        if (R > r) op[L - 1].emplace_back(r + 1, R, id, 1), R = r;
        if (L < l) op[R].emplace_back(L, l - 1, id, -1), L = l;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < MAX; j++) cnt[j] += ((a[i] ^ j ^ A) + (a[i] ^ j ^ B) >= K);
        if (i < n) pre1[i + 1] = pre1[i] + cnt[a[i + 1]];
        pre2[i] = pre2[i - 1] + cnt[a[i]];
        for (auto [l, r, id, coef] : op[i]) for (int j = l; j <= r; j++) ans[id] += coef * cnt[a[j]];
    }
    for (int i = 1, L = 1, R = 0; i <= q; i++) {
        auto [l, r, id] = ask[i];
        ans[id] += ans[get<2>(ask[i - 1])];
        if (R < r) ans[id] += pre1[r] - pre1[R], R = r;
        if (L > l) ans[id] -= pre2[L - 1] - pre2[l - 1], L = l;
        if (R > r) ans[id] -= pre1[R] - pre1[r], R = r;
        if (L < l) ans[id] += pre2[l - 1] - pre2[L - 1], L = l;
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

:::

## [pF. 堆雪人](https://tioj.ck.tp.edu.tw/problems/2327)

Setter：becaido

### Subtask 1：$x\leq 10^ 5,b=1$

$b^y=1,A=\dfrac{a^x}{b^y}=\dfrac{a^x}{1}=a^x,B=0$

只要算 $a^x\text{ mod }N$ 是多少就好了，直接乘是 $O(x)$ 的。

### Subtask 2：$b=1$

用快速冪，$O(\log C)$。

### Subtask 3：$y=1,b<N,N$ 是質數

$B=a^x\text{ mod }b$

$a^x=Ab+B,a^x-B=Ab,A=\dfrac{a^x-B}{b}$

$A\equiv \dfrac{a^x-B}{b}\equiv (a^x-B)b^{-1}\ (\text{mod }N)$

複雜度 $O(\log C)$。

### Subtask 4：$y=1$

把運算都變成 $c_1b^1+c_0b^0$ 的形式。

令 $a^x=C_1b+C_0$，那 $A=\lfloor\dfrac{a^x}{b}\rfloor=C_1$，$B=C_0$。

記得在運算時 $c_1$ 要 $\text{mod }N$，複雜度 $O(\log C)$。

### Subtask 5：無其他限制

把運算都寫成 $c_yb^y+c_{y-1}b^{y-1}+\dots+c_1b^1+c_0b^0$ 的形式，兩個數字相乘相當於在做一個多項式乘法，可以 $O(y^2)$ 求出。

最後 $A$ 會等於 $C_y$，$B$ 等於剩下的人相加，記得運算過程 $c_y$ 要 $\text{mod }N$。

複雜度 $O(y^2\log C)$。

令一個可能的解法是把 $b^y$ 展開來變成大數，然後做 Subtask 4，不過我沒試，常數可能要夠好才會過。

:::spoiler code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ds = vector<int>;

int a, b, x, y, N, M;

ds init(int val) {
    ds re(y + 1, 0);
    for (int i = 0; i < y; i++) {
        re[i] = val % b;
        val /= b;
    }
    re[y] = val % N;
    return re;
}
ds operator * (const ds &l, const ds &r) {
    vector<ll> sum(2 * y + 1, 0);
    for (int i = 0; i <= y; i++) {
        for (int j = 0; j <= y; j++) sum[i + j] += 1ll * l[i] * r[j];
        for (int j = i; j < y; j++) {
            sum[j + 1] += sum[j] / b;
            sum[j] %= b;
        }
        for (int j = y; j <= i + y; j++) sum[j] %= N;
    }
    for (int i = 2 * y; i > y; i--) sum[i - 1] = (sum[i - 1] + sum[i] * b) % N;
    ds re(y + 1, 0);
    for (int i = 0; i <= y; i++) re[i] = sum[i];
    return re;
}
ds power(int d, int up) {
    ds re, nd;
    re = init(1), nd = init(d);
    while (up) {
        if (up & 1) re = re * nd;
        nd = nd * nd;
        up >>= 1;
    }
    return re;
}
int power(int d, int up, int mod) {
    int re = 1;
    d %= mod;
    while (up) {
        if (up & 1) re = 1ll * re * d % mod;
        d = 1ll * d * d % mod;
        up >>= 1;
    }
    return re;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> a >> b >> x >> y >> N >> M;
    if (b == 1) {
        cout << power(a, x, N) << ' ' << 0 << '\n';
        return 0;
    }
    ds ans = power(a, x);
    int A = ans[y], B = 0;
    for (int i = y - 1; i >= 0; i--) B = (1ll * B * b + ans[i]) % M;
    cout << A << ' ' << B << '\n';
}

:::

:::spoiler Bonus
$y$ 可以到 $10^5$
:::