The 2025 ICPC Asia East Continent Online Contest (II)——D. Arcane Behemoths · znzryb

## 思路讲解

这个就是我们这个数在 rank=2 到 rank=i 的总和。

```cpp
    FOR(i, 2, N) {
        ll lans = 0;
        lans = binpow(2, N - i) * (binpow(3, i - 1) - 1);
        lans %= mod;
        lans *= inv2;
        lans %= mod;
        lans *= A[i];
        lans %= mod;
        ans += lans;
        ans %= mod;
    }
```

rank=1 的时候的贡献。

```cpp
    FOR(i, 1, N) {
        ll lans = binpow(2, N - i) * A[i];
        lans %= mod;
        ans += lans;
        ans %= mod;
    }
```

## AC代码

[https://qoj.ac/submission/1345581](https://qoj.ac/submission/1345581)



::: 源代码

```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())

using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v)
        _print(i), cerr << " ";
    cerr << "]";
}
template <typename T> void _print(set<T> s) {
    cerr << "{ ";
    for (T i : s)
        _print(i), cerr << " ";
    cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
    cerr << "{";
    _print(p.first);
    cerr << ", ";
    _print(p.second);
    cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
    cerr << "{ ";
    for (auto &p : m)
        _print(p), cerr << " ";
    cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
    cerr << "{\n";
    for (auto i : v)
        _print(i), cerr << "\n";
    cerr << " }";
}
#endif

using ll = long long;
using ull = unsigned long long;
using ld = double;
using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<ld>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    while (lT--)
        __();
    return 0;
}
/*

*/
ll binpow(ll a, ll k) {
    a %= mod;
    ll res = 1;
    if (k < 0)
        return 1;
    while (k) {
        if (k & 1) {
            res *= a;
            res %= mod;
        }
        k >>= 1;
        a *= a;
        a %= mod;
    }
    return res;
}
inline void __() {
    cin >> N;
    vll A(N + 5);
    FOR(i, 1, N) { cin >> A[i]; }
    sort(A.begin() + 1, A.begin() + N + 1);
    ll ans = 0;
    ll inv2 = binpow(2, mod - 2);
    FOR(i, 2, N) {
        ll lans = 0;
        lans = binpow(2, N - i) * (binpow(3, i - 1) - 1);
        lans %= mod;
        lans *= inv2;
        lans %= mod;
        lans *= A[i];
        lans %= mod;
        ans += lans;
        ans %= mod;
    }
    // #ifdef LOCAL
    //     cerr << "OK/n";
    // #endif
    FOR(i, 1, N) {
        ll lans = binpow(2, N - i) * A[i];
        lans %= mod;
        ans += lans;
        ans %= mod;
    }
    ans %= mod;
    if (ans < 0)
        ans += mod;
    cout << ans << "\n";
}
/*
AC
https://qoj.ac/submission/1345581
*/
```


:::


## 心路历程（WA，TLE，MLE……）