Para cualquier subsecuencia \( S \), se cumple que \( \text{inv}(S) \leq \text{inv}(p) \), con igualdad si y solo si todos los pares \( (i, j) \) tales que \( i < j \) y \( a_i > a_j \) están presentes en \( S \). Un elemento \( i \) debe incluirse en \( S \) si existe algún \( j < i \) con \( a_j > a_i \) o algún \( j > i \) con \( a_j < a_i \). Este criterio puede verificarse mediante el cálculo previo de máximos por prefijo y mínimos por sufijo.

Si hay \( k \) elementos que no son obligatorios para formar una subsecuencia con el máximo número de invertiones, entonces el número total de subsecuencias válidas es \( 2^k \). En el caso especial donde todos los elementos son opcionales (\( k = n \)), debemos excluir la subsecuencia vacía, resultando en \( 2^n - 1 \).

Complejidad: \( O(n) \).

using namespace std; using ll = long long;

const int mod = 998244353;

struct mint { ll x; mint(ll x = 0) : x((x % mod + mod) % mod) {}

mint operator-() const { return mint(-x); }

mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
}

mint& operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
}

mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
}

mint operator+(const mint a) const {
    return mint(*this) += a;
}

mint operator-(const mint a) const {
    return mint(*this) -= a;
}

mint operator*(const mint a) const {
    return mint(*this) *= a;
}

mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
}

mint inv() const {
    return pow(mod - 2);
}

mint& operator/=(const mint a) {
    return *this *= a.inv();
}

mint operator/(const mint a) const {
    return mint(*this) /= a;
}

};

istream& operator>>(istream& is, mint& a) { return is >> a.x; }

ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

void solve() { int n; cin >> n;

vector<int> p(n);
rep(i, n) cin >> p[i];

vector<int> left_max(n), right_min(n);
int max_val = 0, min_val = n + 1;

rep(i, n) {
    max_val = max(max_val, p[i]);
    if (p[i] == max_val) left_max[i] = 1;
    
    min_val = min(min_val, p[n - 1 - i]);
    if (p[n - 1 - i] == min_val) right_min[n - 1 - i] = 1;
}

int optional_count = 0;
rep(i, n) optional_count += left_max[i] * right_min[i];

mint result = mint(2).pow(optional_count);
if (optional_count == n) result -= 1;

cout << result << '\n';

}

int main() { int t; cin >> t;

while (t--) solve();

return 0;

}

</details>T2. Cadenas balanceadas de 0 y 1
--------------------------------

Se utiliza búsqueda binaria sobre el valor máximo permitido de desequilibrio. Para un valor medio \\( mid \\), se verifica si es posible dividir la cadena en segmentos donde el número de ceros dentro del segmento sea \\( \\leq mid \\), y además el número de unos fuera de ese segmento también sea \\( \\leq mid \\).

Para cada inicio posible, se busca el mayor final tal que el conteo de ceros no exceda \\( mid \\), y luego se comprueba si el resto de unos está dentro del límite. Esto permite una solución en \\( O(|S| \\log |S|) \\).

<details><summary>Implementación</summary>```
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    
    vector<int> prefix_sum(n + 1, 0);
    rep(i, n) prefix_sum[i + 1] = prefix_sum[i] + (s[i] == '0');
    
    vector<int> ones_positions;
    rep(i, n) if (s[i] == '1') ones_positions.push_back(i);
    
    int total_ones = ones_positions.size();
    int low = -1, high = total_ones;
    
    while (high - low > 1) {
        int mid = (low + high) / 2;
        bool valid = false;
        
        rep(i, mid + 1) {
            int start = ones_positions[i];
            int end = ones_positions[total_ones - 1 - mid + i] + 1;
            
            if (prefix_sum[end] - prefix_sum[start] <= mid) {
                valid = true;
                break;
            }
        }
        
        if (valid) high = mid;
        else low = mid;
    }
    
    cout << high << '\n';
}

int main() {
    int t;
    cin >> t;
    
    while (t--) solve();
    
    return 0;
}

Dado un árbol con raíz en \( x \), si el destino \( y \) coincide con \( x \), entonces cada arista en el camino desde \( x \) hasta cualquier punto clave será recorrida dos veces (ida y vuelta). El orden de visita a los puntos clave no afecta el costo mínimo, ya que siempre se puede seguir un recorrido DFS completo.

Cuando \( y \neq x \), se considera \( y \) como un punto clave adicional. Se calcula el costo total como el doble del número de aristas únicas visitadas desde \( x \) hacia todos los puntos clave (incluyendo \( y \)), y luego se resta la distancia desde \( x \) hasta \( y \), porque al final no es necesario regresar.

Complejidad: \( O(n) \).

using namespace std;

void solve() { int n, k, x, y; cin >> n >> k >> x >> y; --x; --y;

vector<int> keys(k);
rep(i, k) cin >> keys[i], --keys[i];

keys.push_back(y);

vector<vector<int>> children(n);
rep(i, n - 1) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    children[u].push_back(v);
    children[v].push_back(u);
}

vector<int> parent(n, -1), depth(n, 0);
auto dfs = [&](auto& self, int node) -> void {
    for (int neighbor : children[node]) {
        if (neighbor == parent[node]) continue;
        parent[neighbor] = node;
        depth[neighbor] = depth[node] + 1;
        self(self, neighbor);
    }
};

dfs(dfs, x);

int total_cost = 0;
vector<bool> visited(n, false);
visited[x] = true;

for (int node : keys) {
    while (!visited[node]) {
        visited[node] = true;
        total_cost += 2;
        node = parent[node];
    }
}

total_cost -= depth[y];

cout << total_cost << '\n';

}

int main() { int t; cin >> t;

while (t--) solve();

return 0;

}

</details>T4. Caminata aleatorai
----------------------

Sea \\( P(i,j) \\) la probabilidad de que el intervalo \\( \[l,r\] \\) sea \\( \[i,j\] \\) después de cierto número de pasos. Se sabe que \\( P(i,i) = \\frac{1}{n} \\) y \\( P(1,n) = 1 \\). Para intervaols intermedios, se define una ecuación recursiva basada en movimientos hacia izquierda o derecha.

Se demuestra que para \\( 1 &lt; i \\leq j &lt; n \\), \\( P(i,j) = \\frac{1}{n} \\). Para los bordes, se obtienen fórmulas cerradas:

- Si \\( i = 1 \\) y \\( j &lt; n \\): \\( P(1,j) = \\frac{j+1}{2n} \\)
- Si \\( j = n \\) y \\( i &gt; 1 \\): \\( P(i,n) = \\frac{n-i+2}{2n} \\)

La contribución esperada de cada posición \\( i \\) al resultado total es proporcional a \\( a\_i \\) multiplicado por el número esperado de veces que \\( i \\) fue incluido durante las expansiones iniciales. Esta suma se expresa como:

\[ \left(1 + \sum_{r &lt; i} P(1,r) + \sum_{1 &lt; l \leq r &lt; i} P(l,r) + \sum_{i &lt; l} P(l,n) + \sum_{i &lt; l \leq r &lt; n} P(l,r)\right) \times a_i \] Al sustituir las fórmulas cerradas y simplificar, se obtiene una expresión algebraica que puede evaluarse en \\( O(n) \\).

<details><summary>Implementación</summary>```
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

const int mod = 666528221;

struct mint {
    ll x;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    
    mint operator-() const { return mint(-x); }
    
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    
    mint operator+(const mint a) const {
        return mint(*this) += a;
    }
    
    mint operator-(const mint a) const {
        return mint(*this) -= a;
    }
    
    mint operator*(const mint a) const {
        return mint(*this) *= a;
    }
    
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    mint inv() const {
        return pow(mod - 2);
    }

    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }

    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};

istream& operator>>(istream& is, mint& a) {
    return is >> a.x;
}

ostream& operator<<(ostream& os, const mint& a) {
    return os << a.x;
}

ll c2(ll n) {
    return n * (n - 1) / 2;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    mint total = 0;
    rep(i, n) {
        mint coef = 1;
        coef += mint(c2(i + 2) - 1) / (2 * n);
        coef += mint(c2(i)) / n;
        coef += mint(c2(n - i + 1) - 1) / (2 * n);
        coef += mint(c2(n - i - 1)) / n;
        total += coef * a[i];
    }
    
    cout << total << '\n';
    
    return 0;
}