---
# System prepended metadata

title: 2024 ICPC Asia Taiwan Online Programming Contest

---

2024 ICPC Asia Taiwan Online Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/105383

比賽影片
---
No

記分板
---
是GBC不是MyGO!!!
![image](https://hackmd.io/_uploads/Syzr-V1R0.png)
![image](https://hackmd.io/_uploads/ryqhHAICA.png)


題解
---
### A. Animal Farm
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=

```
:::

### B. Business Magic
---
#### 題目摘要


#### 想法


:::spoiler 實作

```cpp=
```
:::


### C. Cards
---
#### 題目摘要

#### 想法


:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

struct FenwickTree{
    vector<ll> BIT;
    FenwickTree(int n) : BIT(n + 1, 0) {}

    void mod(int x, ll val) {
        while(x < BIT.size()){
            BIT[x] += val;
            x += x & -x;
        }
    }

    ll query(int x) {
        ll res = 0;
        while (x) {
            res += BIT[x];
            x -= x & -x;
        }
        return res;
    }

    ll rquery(int l, int r) {
        return query(r) - query(l - 1);
    }
};

void solve() {
    int n; cin >> n;
    vector<pii> p(n);
    for (auto &[a, b] : p) cin >> a;
    for (auto &[a, b] : p) cin >> b;
    sort(all(p));
    FenwickTree bit(n);
    ll cnt = 0;
    for (auto [a, b] : p) {
        cnt += b - 1 - bit.query(b);
        bit.mod(b, 1);
    }
    if (cnt & 1) {
        cout << "No\n";
        return;
    }
    cnt /= 2;
    FenwickTree bit2(n);
    vector<int> pos(n + 1), ans;
    rep (i, 0, n) pos[p[i].S] = p[i].F;
    rep (i, 1, n + 1) {
        ll sub = pos[i] + bit2.query(pos[i]) - i;
        if (cnt > sub) {
            bit2.mod(1, 1);
            bit2.mod(pos[i], -1);
            cnt -= sub;
            ans.pb(pos[i] - 1);
        } else {
            int idx;
            rep (j, 0, n) {
                if (p[j].S >= i) {
                    if (p[j].S == i) idx = ans.size();
                    ans.pb(j);
                }
            }
            while (cnt) {
                cnt--;
                swap(ans[idx], ans[idx - 1]);
                idx--;
            }
            break;
        }
    }
    assert(cnt == 0);
    cout << "Yes\n";
    for (int x : ans) cout << p[x].F << ' ';
    cout << '\n';
    for (int x : ans) cout << p[x].S << ' ';
    cout << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::

### D. Disbursement on Quarantine Policy
---
#### 題目摘要
#### 想法


:::spoiler 實作
```cpp=

```
:::

### E. Efficient Slabstones Rearrangement
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=

```
:::

### F. Fibonacci Lucky Numbers
---
#### 題目摘要
#### 想法

:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5, MOD = 10'000'000'000;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX) {
    ll res = 1; 
    while (exp) {
        if(exp & 1) res = __int128(res) * x % mod;
        x = __int128(x) * x % mod;
        exp >>= 1;
    } 
    return res;
}

struct Mat{
    vector<vector<ll>> a;
    int x, y;
    Mat(int _x, int _y){
        a.resize(_x, vector<ll>(_y, 0));
        x = _x;
        y = _y;
    }
    Mat operator * (Mat &inp){
        Mat res(x, inp.y);
        rep(i, 0, x) rep(j, 0, inp.y) rep(k, 0, y){
            res.a[i][j] += __int128(a[i][k]) * inp.a[k][j] % MOD;
            res.a[i][j] %= MOD;
        }
        return res;
    }
};

void powpow(Mat &res, ll exp){
    Mat base = res;
    while(exp){
        if(exp & 1) res = res * base;
        base = base * base;
        exp >>= 1;
    }
}

const ll per = 150'000'000'000LL;
const ll phi = 40'000'000'000LL;
const ll phi2 = 16'000'000'000LL; 

void solve() {
    int n; cin >> n;
    // 7^7^7^n (mod per) -> 7^(7^7^n (mod phi)) (mod per) -> 7^(7^(7^n (mod phi2)) (mod phi)) (mod per)
    ll p3 = fpow(7, n, phi2);
    ll p2 = fpow(7, p3, phi);
    ll p1 = (fpow(7, p2, per) - 1 + per) % per;
    Mat fib(2, 2); // [1, 1], [1, 0]
    fib.a[0][0] = fib.a[0][1] = fib.a[1][0] = 1;
    fib.a[1][1] = 0;
    powpow(fib, p1);
    string ans = to_string(fib.a[0][1]);
    while (ans.size() < 10) ans = '0' + ans;
    cout << ans << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}
```
:::

### G. Game of Rounding
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=

```
:::


### H. Harmonious Passage of Magicians
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=

```
:::

### I. In Search of the Lost Array
---
#### 題目摘要
#### 想法

:::spoiler 實作
```cpp=


```
:::


### J. Just Round Down
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=


```
:::


### K. Kingdom's Development Plan
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=


```
:::

### L. Lexicopolis
---
#### 題目大綱

#### 想法

:::spoiler 實作
```cpp=
#ifdef LOCAL
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second

#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif

void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD2 = 998244353, IINF = 1e9 + 7, MOD = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow (ll x, ll exp, ll mod = LLONG_MAX) { if (x == 0) return 0; ll res = 1; while (exp > 0) { if (exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1; } return res; }

#define int long long

void solve() {
    int n, m, ss, tt, x, step; cin >> n >> m >> ss >> tt >> x >> step;
    ss--, tt--;
    
    // dp[i][j][t]: from i->j, length 2^t. pair: {rank (relative to same t), hash}
    // dp[i][j][t] <- dp[i][k][t - 1] + dp[k][j][t - 1], min lexi.(compare {r1, r2}), hash = h1 * x^{2^{t-1}} + h2
    // maybe 離散化 the rank after each round doubling
    
    vector<int> X(30);
    rep (i, 0, 30) X[i] = fpow(x, (1 << i), MOD);

    vector dp(30, vector (n, vector<pii>(n, pii(-1, -1))));
    rep (i, 0, m) {
        int a, b, w; cin >> a >> b >> w;
        a--, b--;
        dp[0][a][b] = pii(w, w);
    }

    auto lisan = [&](vector<vector<pii>> &arr) -> void {
        vector<int> dic;
        rep (i, 0, n) rep (j, 0, n) if (arr[i][j].fi != -1) {
            dic.pb(arr[i][j].fi);
        }
        sort(all(dic));
        dic.erase(unique(all(dic)), dic.end());
        rep (i, 0, n) rep (j, 0, n) if (arr[i][j].fi != -1) {
            arr[i][j].fi = lower_bound(all(dic), arr[i][j].fi) - dic.begin();
        }
    };
    
    // build doubling
    lisan(dp[0]);
    rep (t, 1, 30) {
        rep (k, 0, n) rep (i, 0, n) rep (j, 0, n) {
            auto &[r1, h1] = dp[t - 1][i][k];
            auto &[r2, h2] = dp[t - 1][k][j];
            auto &[r, h] = dp[t][i][j];
            if (r1 == -1 || r2 == -1) continue;
            if (r == -1 || r > r1 * (n * n) + r2) {
                r = r1 * (n * n) + r2;
                h = (h1 * X[t - 1] + h2) % MOD;
            }
        }
        lisan(dp[t]);
    }

    // jump
    vector cur(n, vector<pii>(n, pii(-1, -1)));
    cur[ss][ss] = {0, 0};

    rep (t, 0, 30) if (step >> t & 1) {
        vector nxt(n, vector<pii>(n, pii(-1, -1)));
        rep (k, 0, n) rep (i, 0, n) rep (j, 0, n) {
            auto &[r1, h1] = cur[i][k];
            auto &[r2, h2] = dp[t][k][j];
            auto &[r, h] = nxt[i][j];
            if (r1 == -1 || r2 == -1) continue;
            if (r == -1 || r > r1 * (n * n) + r2) {
                r = r1 * (n * n) + r2;
                h = (h1 * X[t] + h2) % MOD;
            }
        }
        swap(cur, nxt);
        lisan(cur);
    }

    cout << cur[ss][tt].se << '\n';
}
 
signed main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::