ARC142 E Pairing Wizards

Classify nodes as valid if their final $a_u \geq b_u$. Invalid nodes must have $b_u$ strictly larger than the $b$ value of all adjacent nodes, meaning invalid nodes are non-adjacent and form an independent set. This splits the graph into a bipartition between valid and invalid candidates, suitable for min-cut modeling.

First compute mandatory base costs: for valid node candidates, raise $a_u$ to at least $b_u$ if it is lower. For invalid node candidates, raise $a_u$ to at least the maximum $b$ value of all neighbors. Remaining constraints require for each edge $(u,v)$ either $u$ is valid or $v$ is valid to satisfy edge requirements.

Use a value-split min-cut model to encode max-contribution requirements: split each valid candidate node into a chain of nodes corresponding to possible $a$ values, connect edges to prefixes of the chain to enforce that cutting a position in the chain corresponds to raising $a_u$ to that value. Compute the min cut of the constructed graph to get the minimal extra cost, added to the base cost for the final answer.

int fast_read() { char c = getchar(); int res = 0; while(c < 48 || c > 57) c = getchar(); do { res = (res << 1) + (res << 3) + (c ^ 48); c = getchar(); } while(c >= 48 && c <= 57); return res; }

const int MAXN = 105; const int INF = 0x3f3f3f3f; int node_cnt, edge_cnt; int cur_a[MAXN], req_b[MAXN]; vector adj[MAXN]; bool is_invalid[MAXN]; int split_id[MAXN], total_nodes;

int main() { node_cnt = fast_read(); for(int i = 1; i <= node_cnt; ++i) { cur_a[i] = fast_read(); req_b[i] = fast_read(); } edge_cnt = fast_read(); for(int i = 1; i <= edge_cnt; ++i) { int u = fast_read(), v = fast_read(); adj[u].push_back(v); adj[v].push_back(u); } long long base_cost = 0; int source = total_nodes++, sink = total_nodes++;

for(int u = 1; u <= node_cnt; ++u) {
    is_invalid[u] = true;
    for(int v : adj[u]) {
        if(req_b[v] >= req_b[u]) {
            is_invalid[u] = false;
            break;
        }
    }
    if(is_invalid[u]) {
        for(int v : adj[u]) {
            if(cur_a[u] < req_b[v]) {
                base_cost += req_b[v] - cur_a[u];
                cur_a[u] = req_b[v];
            }
        }
        split_id[u] = total_nodes++;
    } else {
        if(cur_a[u] < req_b[u]) {
            base_cost += req_b[u] - cur_a[u];
            cur_a[u] = req_b[u];
        }
        split_id[u] = total_nodes;
        total_nodes += 100 - cur_a[u];
    }
}

atcoder::mf_graph<int> flow_graph(total_nodes);
for(int u = 1; u <= node_cnt; ++u) {
    if(is_invalid[u]) {
        if(cur_a[u] < req_b[u]) {
            flow_graph.add_edge(source, split_id[u], req_b[u] - cur_a[u]);
            for(int v : adj[u]) {
                if(cur_a[v] < req_b[u]) {
                    for(int i = 0; i < req_b[u] - cur_a[v]; ++i) {
                        flow_graph.add_edge(split_id[u], split_id[v] + i, INF);
                    }
                }
            }
        }
    } else {
        for(int i = 0; i < 100 - cur_a[u]; ++i) {
            flow_graph.add_edge(split_id[u] + i, sink, 1);
        }
    }
}
printf("%lld\n", base_cost + flow_graph.flow(source, sink));
return 0;

}

</details>

### ARC142 D Deterministic Placing
Valid configurations toggle between exactly two distinct states on each operation, as all moves are reversible. Each token's movement path covers exactly two nodes, and connected components of overlapping paths form linear chains, each with exactly two valid initial states.

The problem reduces to partitioning the input tree into chains of length at least 2, with no chain endpoint adjacent to a non-endpoint node of another chain. Use tree DP with four states for each node:
- `head[u]`: u is the head of an incomplete chain extending into its subtree
- `body[u]`: u is an internal node of a chain
- `tail[u]`: u is the tail of an incomplete chain extending out of its subtree
- `closed[u]`: u is part of a fully closed chain within its subtree

Compute the DP values via post-order traversal, then combine results for the root node to get the total number of valid configurations multiplied by 2 (for the two initial states per chain).

<details><summary>Code</summary>
```cpp
#include <cstdio>
using namespace std;

int fast_read() {
    char c = getchar();
    int res = 0;
    while(c < 48 || c > 57) c = getchar();
    do {
        res = (res << 1) + (res << 3) + (c ^ 48);
        c = getchar();
    } while(c >= 48 && c <= 57);
    return res;
}

const int MOD = 998244353;
const int MAXN = 200005;
typedef long long ll;
int head[MAXN], to[MAXN << 1], nxt[MAXN << 1], edge_cnt;

inline void add_edge(int u, int v) {
    nxt[++edge_cnt] = head[u];
    head[u] = edge_cnt;
    to[edge_cnt] = v;
}

int n;
ll ch_head[MAXN], ch_body[MAXN], ch_tail[MAXN], ch_closed[MAXN];

void dfs(int u, int fa) {
    ch_tail[u] = 1;
    ll prod = 1, tmp = 0;
    for(int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if(v == fa) continue;
        dfs(v, u);
        ch_head[u] = (ch_tail[u] * (ch_body[v] + ch_tail[v]) % MOD + ch_head[u] * ch_head[v] % MOD) % MOD;
        ch_body[u] = (prod * (ch_body[v] + ch_tail[v]) % MOD + ch_body[u] * ch_closed[v] % MOD) % MOD;
        ch_closed[u] = (tmp * (ch_body[v] + ch_tail[v]) % MOD + ch_closed[u] * ch_closed[v] % MOD) % MOD;
        tmp = (prod * (ch_body[v] + ch_tail[v]) % MOD + tmp * ch_closed[v] % MOD) % MOD;
        prod = prod * ch_closed[v] % MOD;
        ch_tail[u] = ch_tail[u] * ch_head[v] % MOD;
    }
    ch_closed[u] = ch_closed[u] * 2 % MOD;
}

int main() {
    n = fast_read();
    for(int i = 1; i < n; ++i) {
        int u = fast_read(), v = fast_read();
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(1, 0);
    ll res = ch_head[1] * 2 % MOD;
    res = (res + ch_closed[1]) % MOD;
    printf("%lld\n", res);
    return 0;
}

ARC141 F Well-defined Abbreviation

To determine if all substring deletion sequences produce the same final result, first filter out non-primitive strings that can be formed by concatenating and deleting other strings from the input set.

Build an AC automaton for all input strings. Process each string by traversing the automaton, rolling back the current position whenever a matched suffix is found. If the string is fully erased during this process, it is non-primitive and can be ignored. If any string is not fully erased, multiple deletion sequences exist, so the answer is "Yes".

For remaining primitive strings, check for overlapping prefix-suffix pairs: if any pair has an asymmetric overlap that is not bidirectional, ambiguous deletion order exists, output "Yes". If all checks pass, output "No".

const int MAXNODE = 2000005; __gnu_pbds::gp_hash_table<int, int> overlap_map[MAXNODE]; int n, str_len[MAXN]; char *str[MAXN], buf[MAXNODE]; int stk[MAXNODE], stk_top; int trie[MAXNODE][4], node_cnt = 1; int fail[MAXNODE], depth[MAXNODE], que[MAXNODE], que_tail; bool is_end[MAXNODE], is_primitive[MAXN]; int jump[MAXNODE], end_pos[MAXN], str_id[MAXNODE];

int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%s", buf); str_len[i] = strlen(buf); str[i] = new char[str_len[i]]; memcpy(str[i], buf, str_len[i]); int p = 1; for(int j = 0; j < str_len[i]; ++j) { int c = buf[j] - 'A'; if(!trie[p][c]) { trie[p][c] = ++node_cnt; depth[trie[p][c]] = j + 1; } p = trie[p][c]; } is_end[p] = 1; end_pos[i] = p; } for(int c = 0; c < 4; ++c) trie[0][c] = 1; que[que_tail = 1] = 1; for(int i = 1; i <= que_tail; ++i) { int u = que[i]; if(is_end[u]) jump[u] = depth[u]; if(jump[fail[u]]) jump[u] = jump[fail[u]]; for(int c = 0; c < 4; ++c) { if(trie[u][c]) { fail[trie[u][c]] = trie[fail[u]][c]; que[++que_tail] = trie[u][c]; } else { trie[u][c] = trie[fail[u]][c]; } } } for(int i = 1; i <= n; ++i) { stk_top = 0; stk[0] = 1; is_primitive[i] = 1; for(int j = 0; j < str_len[i]; ++j) { int c = str[i][j] - 'A'; stk[stk_top + 1] = trie[stk[stk_top]][c]; stk_top++; if(jump[stk[stk_top]]) { if(stk_top < str_len[i]) is_primitive[i] = 0; stk_top -= jump[stk[stk_top]]; } } if(stk_top) { puts("Yes"); return 0; } } for(int i = 1; i <= n; ++i) { if(is_primitive[i]) { int p = 1; for(int j = 0; j < str_len[i]; ++j) { int c = str[i][j] - 'A'; p = trie[p][c]; if(str_id[p]) str_id[p] = -1; else str_id[p] = i; } } } for(int i = 1; i <= n; ++i) { if(is_primitive[i]) { int p = end_pos[i]; while(fail[p] > 1) { p = fail[p]; if(str_id[p] < 0) { puts("Yes"); return 0; } int j = str_id[p]; if(!j) continue; overlap_map[i][depth[p]] = j; if(str_len[i] != str_len[j]) { puts("Yes"); return 0; } } } } for(int i = 1; i <= n; ++i) { if(is_primitive[i]) { int p = end_pos[i]; while(fail[p] > 1) { p = fail[p]; int j = str_id[p]; if(!j) continue; if(overlap_map[j][str_len[i] - depth[p]] != i) { puts("Yes"); return 0; } } } } puts("No"); return 0; }

</details>

### ARC141 E Sliding Edge on Torus
Map each diagonal equivalence class on the torus to a node. Each operation adds a constraint that the difference between the state values of two nodes equals a fixed modulo value. This is a classic weighted union-find (disjoint set union, DSU) problem with additional tracking of the gcd of all cycle lengths in each connected component.

For each connected component, the number of reachable states is equal to the gcd of all cycle lengths. Maintain the total number of reachable states across all components, updating it as edges are added. When merging two components, compute the new gcd for the merged component and adjust the total accordingly.

<details><summary>Code</summary>
```cpp
#include <cstdio>
using namespace std;

int fast_read() {
    char c = getchar();
    int res = 0;
    while(c < 48 || c > 57) c = getchar();
    do {
        res = (res << 1) + (res << 3) + (c ^ 48);
        c = getchar();
    } while(c >= 48 && c <= 57);
    return res;
}

const int MAXN = 200005;
typedef long long ll;
int mod, q;
int parent[MAXN], gcd_val[MAXN], weight[MAXN];

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

void path_compress(int u) {
    if(parent[u] == u) return;
    path_compress(parent[u]);
    weight[u] = (weight[u] + weight[parent[u]]) % mod;
    parent[u] = parent[parent[u]];
}

int main() {
    mod = fast_read();
    q = fast_read();
    ll total = 0;
    for(int i = 0; i < mod; ++i) {
        parent[i] = i;
        gcd_val[i] = mod;
        weight[i] = 0;
        total += mod;
    }
    for(int i = 0; i < q; ++i) {
        int a = fast_read(), b = fast_read(), c = fast_read(), d = fast_read();
        int x = (b - a + mod) % mod;
        int y = (d - c + mod) % mod;
        int z = (d - b + mod) % mod;
        path_compress(x);
        path_compress(y);
        if(parent[x] != x) {
            z = (z + mod - weight[x]) % mod;
            x = parent[x];
        }
        if(parent[y] != y) {
            z = (z + weight[y]) % mod;
            y = parent[y];
        }
        if(x == y) {
            total -= gcd_val[x];
            gcd_val[x] = gcd(gcd_val[x], z);
            total += gcd_val[x];
        } else {
            total -= gcd_val[x] + gcd_val[y];
            parent[x] = y;
            weight[x] = z;
            gcd_val[y] = gcd(gcd_val[x], gcd_val[y]);
            total += gcd_val[y];
        }
        printf("%lld\n", total);
    }
    return 0;
}

ARC141 D Non-divisible Set

The problem reduces to finding the maximum antichain in a partial order where edges go from each number to its multiples. By Dilworth's theorem, the maximum antichain size equals the minimum chain cover size. Construct a chain cover by grouping numbers by their odd part: each chain starts with an odd number and includes all its multiples by powers of 2.

For each number, remove all factors of 2 to get its odd part, and record the exponent of 2 in its prime factorization. For the antichain constraint, if odd part $x$ divides odd part $y$, then the exponent of 2 for $x$ must be strictly larger than that for $y$.

Compute the lower and upper bounds for the exponent of 2 for each odd part via topological sort on the odd-part partial order. For each input number, check if its exponent of 2 falls within the valid range for its odd part to determine if it can be included in the maximum antichain.

queue q; int fast_read() { char c = getchar(); int res = 0; while(c < 48 || c > 57) c = getchar(); do { res = (res << 1) + (res << 3) + (c ^ 48); c = getchar(); } while(c >= 48 && c <= 57); return res; }

const int MAXN = 1000005; const int INF = 0x3f3f3f3f; int head[MAXN], to[MAXN << 1], nxt[MAXN << 1], edge_cnt;

inline void add_edge(int u, int v) { nxt[++edge_cnt] = head[u]; head[u] = edge_cnt; to[edge_cnt] = v; }

int n, m; int odd_part[MAXN], exp_2[MAXN]; vector exp_list[MAXN]; vector forward_edge[MAXN], backward_edge[MAXN]; int in_deg_fwd[MAXN], in_deg_bwd[MAXN]; int lower_bound[MAXN], upper_bound[MAXN];

int main() { n = fast_read(); m = fast_read(); for(int i = 0; i < m; ++i) { exp_list[i].emplace_back(-INF); } for(int i = 1; i <= n; ++i) { int x = fast_read(); int cnt = 0; while((x & 1) == 0) { x >>= 1; cnt++; } odd_part[i] = x >> 1; exp_2[i] = cnt; exp_list[odd_part[i]].emplace_back(cnt); } for(int i = 0; i < m; ++i) { if(exp_list[i].size() == 1) { for(int j = 0; j < n; ++j) puts("No"); return 0; } exp_list[i].emplace_back(INF); } for(int i = 0; i < m; ++i) { int x = (i << 1) | 1; for(int y = 3 * x; y < 2 * m; y += 2 * x) { int j = y >> 1; forward_edge[j].emplace_back(i); in_deg_fwd[i]++; backward_edge[i].emplace_back(j); in_deg_bwd[j]++; } } for(int i = 0; i < m; ++i) { lower_bound[i] = -INF; if(in_deg_fwd[i] == 0) q.emplace(i); } while(!q.empty()) { int u = q.front(); q.pop(); if(lower_bound[u] != INF) { lower_bound[u] = *upper_bound(exp_list[u].begin(), exp_list[u].end(), lower_bound[u]); } if(lower_bound[u] == INF) { for(int j = 0; j < n; ++j) puts("No"); return 0; } for(int v : forward_edge[u]) { if(--in_deg_fwd[v] == 0) q.emplace(v); if(lower_bound[v] < lower_bound[u]) lower_bound[v] = lower_bound[u]; } } for(int i = 0; i < m; ++i) { upper_bound[i] = INF; if(in_deg_bwd[i] == 0) q.emplace(i); } while(!q.empty()) { int u = q.front(); q.pop(); if(upper_bound[u] != -INF) { upper_bound[u] = *prev(lower_bound(exp_list[u].begin(), exp_list[u].end(), upper_bound[u])); } if(upper_bound[u] == INF) { for(int j = 0; j < n; ++j) puts("No"); return 0; } for(int v : backward_edge[u]) { if(--in_deg_bwd[v] == 0) q.emplace(v); if(upper_bound[v] > upper_bound[u]) upper_bound[v] = upper_bound[u]; } } for(int i = 1; i <= n; ++i) { if(exp_2[i] >= lower_bound[odd_part[i]] && exp_2[i] <= upper_bound[odd_part[i]]) { puts("Yes"); } else { puts("No"); } } return 0; }

</details>

### ARC140 F ABS Permutation
Rewrite the problem condition as $|p_i - p_{i+m}| = 1$. Group indices by their remainder modulo $m$, reducing the problem to the $m=1$ case where we count permutations of length $n/m$ with adjacent absolute difference 1. The solution uses exponential generating functions (EGF): compute the EGF for valid permutations of length $k$, then raise it to the $m$-th power via fast exponentiation of generating functions.

For the $m=1$ case, valid permutations are constructed by splitting the identity permutation into segments, reversing each segment, and applying inclusion-exclusion to count valid configurations.

### ARC140 E Not Equal Rectangle
To construct a grid with no monochromatic axis-aligned rectangles, ensure that for any color, each unordered pair of columns appears together in at most one row. Use a number-theoretic construction with base $B=23$ (since $23^2 > 500$) to partition row pairs into groups of size $B$, ensuring no duplicate column pairs per color.

Map each cell $(i,j)$ to a color using the formula $color(i,j) = (k + l * i) \mod B$, where $l$ is derived from the column index. This guarantees the no-monochromatic-rectangle property.

<details><summary>Code</summary>
```cpp
#include <cstdio>
using namespace std;

int fast_read() {
    char c = getchar();
    int res = 0;
    while(c < 48 || c > 57) c = getchar();
    do {
        res = (res << 1) + (res << 3) + (c ^ 48);
        c = getchar();
    } while(c >= 48 && c <= 57);
    return res;
}

const int BASE = 23;
const int MAX = 550;
int grid[MAX][MAX];

int main() {
    for(int i = 0; i < BASE; ++i) {
        for(int j = 0; j < BASE; ++j) {
            for(int k = 0; k < BASE; ++k) {
                int x = (i + k) % BASE;
                for(int t = 0; t < BASE; ++t) {
                    grid[i * BASE + j][t * BASE + x] = k;
                    x = (x + j) % BASE;
                }
            }
        }
    }
    int n = fast_read(), m = fast_read();
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            printf("%d ", grid[i][j] + 1);
        }
        putchar('\n');
    }
    return 0;
}

ARC140 D One to One

The input graph is a functional graph consisting of cycles and trees directed towards cycles. The number of connected components equals the number of cycles in the graph. Count valid configurations by first processing existing cycles, then using DP to count ways to form cycles from chains of nodes with undefined next pointers.

Use a knapsack DP to combine chain lengths, multiplying by factorial coefficients to count cyclic permutations of chains into cycles.

int fast_read() { char c = getchar(); int res = 0; bool neg = false; while(c < 48 || c > 57) { neg |= (c == '-'); c = getchar(); } do { res = (res << 1) + (res << 3) + (c ^ 48); c = getchar(); } while(c >= 48 && c <= 57); return neg ? -res : res; }

const int MOD = 998244353; const int MAXN = 2005; typedef long long ll; int parent[MAXN];

int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }

int n, free_cnt; int dp[MAXN], sz[MAXN], pow_n[MAXN]; bool has_cycle[MAXN];

inline void merge(int x, int y) { x = find(x); y = find(y); if(x == y) { has_cycle[x] = true; return; } has_cycle[x] |= has_cycle[y]; parent[y] = x; }

int main() { n = fast_read(); dp[0] = 1; for(int i = 1; i <= n; ++i) parent[i] = i; for(int i = 1; i <= n; ++i) { int x = fast_read(); if(x != -1) merge(x, i); else free_cnt++; } for(int i = 1; i <= n; ++i) sz[find(i)]++; int res = 0, lim = 0; for(int i = 1; i <= n; ++i) { if(find(i) == i) { if(has_cycle[i]) res++; else { for(int x = lim; x >= 0; --x) { dp[x+1] = (dp[x+1] + (ll)dp[x] * sz[i]) % MOD; } lim++; } } } pow_n[0] = 1; for(int i = 1; i <= free_cnt; ++i) { pow_n[i] = (ll)pow_n[i-1] * n % MOD; } res = (ll)res * pow_n[free_cnt] % MOD; int fac = 1; for(int i = 1; i <= lim; ++i) { fac = (ll)fac * i % MOD; res = (res + (ll)pow_n[free_cnt - i] * fac % MOD * dp[i]) % MOD; } printf("%d\n", res); return 0; }

</details>

### ARC138 E Decreasing Subsequence
Map each non-zero element $a_i$ to a directed edge $i \to a_i - 1$. The resulting graph is a collection of chains, with chain heads being nodes connected to 0. A decreasing subsequence of length $2k$ corresponds to selecting $k$ pairs of adjacent nodes in these chains, breaking the chains into three groups: unbroken chains, left segments of broken chains, and right segments of broken chains.

Count valid configurations using Stirling numbers of the second kind (for set partitions) and Bell numbers (for counting partitions of unbroken chains). Enumerate the size of the three groups and combine counts with combinatorial coefficients.

<details><summary>Code</summary>
```cpp
#include <cstdio>
using namespace std;
typedef long long ll;

int fast_read() {
    char c = getchar();
    int res = 0;
    while(c < 48 || c > 57) c = getchar();
    do {
        res = (res << 1) + (res << 3) + (c ^ 48);
        c = getchar();
    } while(c >= 48 && c <= 57);
    return res;
}

const int MOD = 1000000007;
const int MAXN = 5005;
int n, k;
int stirling[MAXN][MAXN], comb[MAXN][MAXN], bell[MAXN];

int main() {
    n = fast_read() + 1;
    k = fast_read();
    comb[0][0] = 1;
    stirling[0][0] = 1;
    bell[0] = 1;
    for(int i = 1; i <= n; ++i) {
        comb[i][0] = 1;
        for(int j = 1; j <= i; ++j) {
            stirling[i][j] = (stirling[i-1][j-1] + (ll)stirling[i-1][j] * j) % MOD;
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
            bell[i] = (bell[i] + stirling[i][j]) % MOD;
        }
    }
    ll res = 0;
    for(int i = k; i <= n; ++i) {
        for(int j = k; i + j <= n; ++j) {
            ll cnt = (ll)comb[n][i+j] * stirling[i][k] % MOD;
            cnt = cnt * stirling[j][k] % MOD;
            cnt = cnt * bell[n - i - j] % MOD;
            res = (res + cnt) % MOD;
        }
    }
    printf("%lld\n", res);
    return 0;
}

ARC139 E Wazir

If both dimensions $n$ and $m$ are even, the answer is 2. If one dimension is even and the other is odd, the maximum number of placements is $(len_{odd} - 1) / 2 * len_{even}$. If both are odd, the upper bound is $\min(n*(m-1)/2, m*(n-1)/2)$, which is always achievable.

Count valid configurations using cyclic convolution and fast exponentiation of generating functions, as valid state transitions are adjacent modulo $n$.

ll qpow(int a, int b = MOD - 2) { ll res = 1; while(b) { if(b & 1) res = res * a % MOD; a = (ll)a * a % MOD; b >>= 1; } return res; }

int rev[1 << 18], cw[1 << 18 | 1]; int len, inv_len;

void ntt_init(int _len) { len = 1; int bt = -1; while(len < _len) { len <<= 1; bt++; } cw[len] = cw[0] = 1; int w = qpow(3, (MOD - 1) >> (bt + 1)); inv_len = qpow(len); for(int i = 1; i < len; ++i) { rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bt); cw[i] = (ll)cw[i-1] * w % MOD; } }

void ntt(int *arr, bool invert) { for(int i = 0; i < len; ++i) { if(i < rev[i]) swap(arr[i], arr[rev[i]]); } for(int i = 1, t = 1; i < len; i <<= 1, ++t) { for(int j = 0; j < len; j += (i << 1)) { for(int k = j, tt = invert ? len : 0; k < (j | i); ++k) { tt += invert ? -(len >> t) : (len >> t); int x = arr[k], y = (ll)arr[k | i] * cw[tt] % MOD; arr[k] = (x + y) % MOD; arr[k | i] = (x - y + MOD) % MOD; } } } if(invert) { for(int i = 0; i < len; ++i) { arr[i] = (ll)arr[i] * inv_len % MOD; } } }

const int MAXN = 1000005; int S[MAXN], R[MAXN]; int fac[MAXN], inv_fac[MAXN];

int main() { ll n, m; scanf("%lld %lld", &n, &m); if((n % 2 == 0) && (m % 2 == 0)) { puts("2"); return 0; } if((n % 2 == 1) && (m % 2 == 1) && n > m) swap(n, m); if((n % 2 == 0) && (m % 2 == 1)) swap(n, m); if(n > m) { fac[0] = 1; for(int i = 1; i <= m; ++i) fac[i] = (ll)fac[i-1] * i % MOD; inv_fac[m] = qpow(fac[m]); for(int i = m; i >= 1; --i) inv_fac[i-1] = (ll)inv_fac[i] * i % MOD; ll res = 0; for(int i = 0; i <= m; ++i) { if((2 * i - m) % n == 0) { res = (res + (ll)inv_fac[i] * inv_fac[m - i]) % MOD; } } res = res * fac[m] % MOD * (n % MOD) % MOD; printf("%lld\n", res); return 0; } ll res = n % MOD; S[1] = S[n - 1] = 1; R[0] = 1; ntt_init(2 * n); while(m) { ntt(S, false); if(m & 1) { ntt(R, false); for(int i = 0; i < len; ++i) R[i] = (ll)R[i] * S[i] % MOD; ntt(R, true); for(int i = 2 * n - 1; i >= n; --i) { R[i - n] = (R[i - n] + R[i]) % MOD; R[i] = 0; } } for(int i = 0; i < len; ++i) S[i] = (ll)S[i] * S[i] % MOD; ntt(S, true); for(int i = 2 * n - 1; i >= n; --i) { S[i - n] = (S[i - n] + S[i]) % MOD; S[i] = 0; } m >>= 1; } res = res * R[0] % MOD; printf("%lld\n", res); return 0; }

</details>

### ARC139 D Priority Queue 2
Convert the problem to 01 indicator variables: for each value $x$, count the expected number of elements greater than $x$ in the priority queue after all operations. Sum these counts over all $x$ to get the expected minimum value.

Use combinatorial counting to compute the probability that $t$ elements greater than $x$ are inserted and deleted over the course of operations, with a time complexity of $O(K + M)$ where $K$ is the number of operations and $M$ is the maximum value.

<details><summary>Code</summary>
```cpp
#include <cstdio>
using namespace std;

int fast_read() {
    char c = getchar();
    int res = 0;
    while(c < 48 || c > 57) c = getchar();
    do {
        res = (res << 1) + (res << 3) + (c ^ 48);
        c = getchar();
    } while(c >= 48 && c <= 57);
    return res;
}

const int MOD = 998244353;
const int MAXK = 2005;
typedef long long ll;
int n, m, k, pos;
int a[MAXK], pow_x[MAXK];
int comb[MAXK][MAXK];

int main() {
    n = fast_read();
    m = fast_read();
    k = fast_read();
    pos = n + 1 - fast_read();
    for(int i = 1; i <= n; ++i) a[i] = fast_read();
    for(int i = 0; i <= k; ++i) {
        comb[i][0] = 1;
        for(int j = 1; j <= i; ++j) {
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
    }
    ll res = 0;
    for(int x = 0; x < m; ++x) {
        int cnt_gt = 0;
        for(int i = 1; i <= n; ++i) {
            if(a[i] > x) cnt_gt++;
        }
        pow_x[0] = 1;
        for(int i = 1; i <= k; ++i) {
            pow_x[i] = (ll)pow_x[i-1] * x % MOD;
        }
        ll pow_mx = 1;
        for(int i = 0; i <= k; ++i) {
            int cur = cnt_gt;
            if(cur > pos) {
                cur -= (k - i);
                if(cur < pos) cur = pos;
            } else {
                cur += i;
                if(cur > pos) cur = pos;
            }
            ll term = (ll)comb[k][i] * pow_x[k - i] % MOD;
            term = term * pow_mx % MOD;
            term = term * cur % MOD;
            res = (res + term) % MOD;
            pow_mx = pow_mx * (m - x) % MOD;
        }
    }
    printf("%lld\n", res);
    return 0;
}