Without the "after sorting condition", there are only two ways to color the cards. We must have that $$$a$$$ is alternating in color.

Without loss of generality, color the odd indices red and the even indices blue. This uniquely colors every card. Now, let's sort the array $$$a$$$, while also keeping track of the colors; one way to do this is by sorting it as a vector of pairs. Then we simply have to verify that no two adjacent cards are the same color.

Alternatively, you can use the fact that $$$a$$$ is a permutation, so all differences of $$$a_i - i$$$ have to either be odd or even.

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a) {
        cin >> i;
    }

    int cnt = 0;
    for(int i = 0; i < n; i++) {
        cnt += (a[i] % 2 != (i + 1) % 2);
    }

    cout << (cnt == 0 || cnt == n? "YES" : "NO") << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Notice that $$$f(l, r) \gt 0$$$ if and only if $$$a[l, r]$$$ contains a zero. Therefore, if $$$a$$$ does not contain any zeros, the answer is $$$\texttt{NO}$$$, because all values of $$$f(l, r)$$$ are zero, so they are all equal.

Conversely, consider the case where there is exactly one zero. Then we can simply place this zero at the very end. Now, for any $$$1 \leq i \leq n-1$$$, we have that $$$f(1, i) = 0$$$, but $$$f(i+1, n) \neq 0$$$, so the answer is $$$\texttt{YES}$$$.

Finally, consider the case where there are at least two zeros. If $$$a$$$ does not contain any ones, then the answer is $$$\texttt{NO}$$$. This is because we can always choose an $$$i$$$ that splits the zeros — that is, $$$a[1, i]$$$ and $$$a[i+1, n]$$$ both contain a zero — then we will have that $$$f(1, i) = f(i+1, n) = 1$$$.

Otherwise, if $$$a$$$ does contain a one, then we can place all of the zeros at the very end. Now, consider any $$$1 \leq i \leq n-1$$$. If $$$a[1, i]$$$ does not contain a zero, then $$$f(1, i) = 0$$$, but $$$f(i+1, n) \neq 0$$$. If $$$a[1, i]$$$ does contain a zero, then it also contains a one (because all ones are before all zeros), so $$$f(1, i) \geq 2$$$. But $$$a[i+1, n]$$$ consists of only zeros, so $$$f(i+1, n) = 1$$$. Therefore, the answer is $$$\texttt{YES}$$$.

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a) {
        cin >> i;
    }

    vector<int> cnt(n + 1);
    for(auto i : a) cnt[i]++;

    if(cnt[0] == 0) cout << "NO\n";
    else if(cnt[1] > 0) cout << "YES\n";
    else cout << (cnt[0] == 1? "YES" : "NO") << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$t$$$ be the sorted version of $$$s$$$. Then if $$$s = t$$$ at any point, the player to move loses, because there is no legal move remaining.

If $$$s = t$$$ at the start of the game, the answer is $$$\texttt{Bob}$$$. Otherwise, we claim the answer is $$$\texttt{Alice}$$$, and she can win on the first turn by choosing all of the indices at which $$$s$$$ and $$$t$$$ differ.

First, we claim this is non-increasing. Let $$$i$$$ be the number of zeros in $$$s$$$, so $$$t[1, i]$$$ consists of only zeros, and $$$t[i+1, n]$$$ consists of only ones. Then for any $$$j$$$ between $$$1$$$ and $$$i$$$, if $$$s_j$$$ and $$$t_j$$$ differ then $$$s_j = 1$$$. Similarly, for any $$$j$$$ between $$$i+1$$$ and $$$n$$$, if $$$s_j$$$ and $$$t_j$$$ differ then $$$s_j = 0$$$. So out of the chosen indices, the indices between $$$1$$$ and $$$i$$$ satisfy $$$s_j = 1$$$, and the indices between $$$i+1$$$ and $$$n$$$ satisfy $$$s_j = 0$$$, so the sequence is non-increasing.

Next, we claim that this sorts the array; in particular, this implies that it changes the array, so it is legal. Furthermore, this wins immediately since Bob has no subsequent move. Indeed, we see that the number of chosen indices between $$$1$$$ and $$$i$$$ is equal to the number of chosen indices between $$$i+1$$$ and $$$n$$$, because we must have that the number of zeros and ones in $$$s$$$ and $$$t$$$ are equal. So the operation simply exchanges all of the ones in $$$s[1, i]$$$ with all of the zeros in $$$s[i+1, n]$$$, thus making $$$s = t$$$ as desired.

#include <bits/stdc++.h>

using namespace std;

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

    string sorted = s;
    sort(sorted.begin(), sorted.end());

    if (s == sorted) {
        cout << "Bob\n";
        return;
    }

    vector<int> idx;
    for(int i = 0; i < n; ++i) {
        if(s[i] != sorted[i]) {
            idx.push_back(i + 1);
        }
    }

    cout << "Alice\n";
    cout << idx.size() << '\n';
    for(auto i : idx) cout << i << " ";
    cout << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

For a string $$$t$$$ to be better than $$$s$$$, note that some prefix of $$$t$$$ will be identical to prefix of $$$s$$$, then at the position $$$i$$$ where $$$t_i \neq s_i$$$, $$$s_i =$$$ $$$)$$$ and $$$t_i =$$$ $$$($$$.

Consider the following greedy algorithm. We try to fix the first position where $$$t_i \neq s_i$$$ and $$$s_i =$$$ $$$)$$$, therefore we have $$$t[1 : i-1]$$$ = $$$s[1 : i - 1]$$$. Now $$$s_i$$$ must be $$$)$$$. To make $$$t$$$ bigger, we look for the first index $$$j \gt i$$$ such that $$$s_j$$$ = $$$($$$. Since this is the next character we add to the subsequence, we must skip the last $$$j - i$$$ characters, which will all be $$$)$$$. For a sequence to be an RBS, it is necessary for it to have equal number of $$$($$$ and $$$)$$$. Therefore, we must atleast skip $$$j - i$$$ more ( after position $$$j$$$ in $$$t$$$.

We can show that if we can have $$$j - i$$$ $$$($$$ brackets after position $$$j$$$ and we delete them, we will always end up with RBS of size $$$n - 2 \times (j - i)$$$.

Therefore, we can simple precompute the next position of $$$($$$ for each index, and find the max over $$$n - 2 \times (j - i)$$$ as long as there are sufficient $$$)$$$ to delete after $$$j$$$.

Time complexity : $$$O(n)$$$

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

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        string s;
        cin >> n >> s;
        vector<int> nx(n + 1, n + 1);
        vector<int> suf(n + 1, 0);
        for(int i = n - 1; i >= 0; i--){
            if(s[i] == '(') nx[i] = i;
            else nx[i] = nx[i + 1];
            if(s[i] == '(') suf[i] += 1;
            suf[i] += suf[i + 1];
        }

        int ans = -1;
        for(int i = 0; i < n; i++){
            if(s[i] == ')' and nx[i] <= n){
                int ig = nx[i] - i;
                if(suf[nx[i] + 1] >= ig){
                    ans = max(ans, n - 2 * ig);
                }
            }
        }

        cout << ans << '\n';
    }
}        

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, read the solution to D1.

We can further observe that if our answer is $$$n - 2 \times k$$$, we must have had $$$((($$$ $$$\cdots$$$ $$$()$$$ followed by $$$k$$$ $$$)$$$ s. If we instead follow the same greedy algorithm at the index of the final $$$($$$, we end up getting $$$k = 1$$$. Therefore, if a good subsequence exists, we can always get a subsequence of length $$$n - 2$$$.

Therefore, a string has a better subsequence of length $$$n - 2$$$ iff it has a "$$$)($$$" followed by "$$$($$$". We can further relax this condition to $$$s$$$ is good if $$$s$$$ is a RBS and it has "$$$)(($$$" as a subsequence.

Now, we can simply count the number of subsequences of different lengths that are an RBS and have a subsequence "$$$)(($$$". This can be done by dynamic programming similar to counting number of subsequences that are RBS.

We define the following DP state:

$$$dp[i][b][l][k]$$$ = number of bracket sequences using first $$$i$$$ characters, with balance $$$b$$$, having length $$$l$$$ and $$$k$$$ indicates how many characters of "$$$)(($$$" occur as a subsequence in the strings.

We obtain the following cases:

• If $$$s[i] =$$$ $$$($$$ and $$$k =$$$ {$$$1, 2$$$}, $$$dp[i][b + 1][l + 1][k + 1]$$$ $$$+= dp[i - 1][b][l][k]$$$

• If $$$s[i] =$$$ $$$($$$ and $$$k =$$$ {$$$0, 3$$$}, $$$dp[i][b + 1][l + 1][k]$$$ $$$+= dp[i - 1][b][l][k]$$$

• If $$$s[i] =$$$ $$$)$$$ and $$$k =$$$ {$$$0$$$} and $$$b \geq 1$$$, $$$dp[i][b - 1][l + 1][k + 1]$$$ $$$+= dp[i - 1][b][l][k]$$$

• If $$$s[i] =$$$ $$$)$$$ and $$$k =$$$ {$$$1, 2, 3$$$} and $$$b \geq 1$$$, $$$dp[i][b - 1][l + 1][k]$$$ $$$+= dp[i - 1][b][l][k]$$$

We finally output answer as the sum over $$$dp[n][0][l][3] \times (l - 2)$$$ over all $$$l$$$.

Time Complexity: $$$O(n^3)$$$. This can also be implemented in $$$O(n^2)$$$ by not storing the length but the sum of lengths and the count separately.

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

// Mint template omitted for readability

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);

Mint C(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    while ((int) fact.size() < n + 1) {
        fact.push_back(fact.back() * (int) fact.size());
        inv_fact.push_back(1 / fact.back());
    }
    return fact[n] * inv_fact[k] * inv_fact[n - k];
}

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        string t = ")((";
        vector<vector<vector<Mint>>> dp(4, vector(n + 1, vector(n + 1, Mint(0)))); // balance, length
        dp[0][0][0] = 1;
        for(int i = 0; i < n; i++){
            auto ndp = dp;
            int add = s[i] == '(' ? 1 : -1;
            for(int bal = 0; bal < n; bal++){
                for(int len = 0; len < n; len++){
                    if(bal + add < 0) continue;
                    for(int ii = 0; ii < 4; ii++){
                        int ni = ii;
                        if(ii == 0 and s[i] == ')') ni++;
                        if((ii == 1 or ii == 2) and s[i] == '(') ni++;
                        ndp[ni][bal + add][len + 1] += dp[ii][bal][len];
                    }
                }
            }
            swap(dp, ndp);
        }

        Mint ans = 0;
        for(int i = 0; i <= n; i++){
            ans += dp[3][0][i] * (i - 2);
        }

        cout << ans << '\n';
    }
}        

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

We require that $$$q \gt p$$$ and $$$\mathbb{rev}(q) \gt \mathbb{rev}(p)$$$. By definition, this is equivalent to the following condition: let $$$i$$$ be the first index at which $$$p$$$ and $$$q$$$ differ, and let $$$j$$$ be the last index at which $$$p$$$ and $$$q$$$ differ. Then we must have that $$$q_i \gt p_i$$$ and $$$q_j \gt p_j$$$.

Now, fix some $$$i \lt j$$$, and consider the subarray $$$p[i, j]$$$. We can rearrange these elements however we want, as long as we increase both endpoints. It is easy to see that this is impossible if $$$p_i$$$ or $$$p_j$$$ is the maximum of the subarray. Otherwise, we want to choose the lexicographically smallest such option. To do so, we set $$$q_i$$$ to be the smallest element in $$$p[i, j]$$$ that is larger than $$$p_i$$$. Then, we place the rest of the elements in ascending order to fill $$$q[i+1, j]$$$.

Let's verify that this is valid. Clearly, $$$q_i \gt p_i$$$ by construction. Now, $$$q_j$$$ is the maximum of $$$q[i+1, j]$$$, so either $$$q_j$$$ or $$$q_i$$$ is the maximum of $$$p[i, j]$$$. If $$$q_j$$$ is the maximum, then it must be larger than $$$p_j$$$ because $$$p_j$$$ is not the maximum. Otherwise, if $$$q_i$$$ is the maximum, then $$$p_i$$$ is the second maximum by construction, so $$$q_j = p_i$$$. Thus, $$$q_j$$$ is larger than $$$p_j$$$ because $$$p_j$$$ is not the maximum or the second maximum.

We conclude that any choice of $$$i \lt j$$$ such that $$$p_i$$$ and $$$p_j$$$ are not the maximum of $$$p[i, j]$$$ yields a valid choice of $$$q$$$, and the optimal one is the one produced by the above construction.

Now, we want to find the choice of $$$i$$$ and $$$j$$$ that yield the lexicographically smallest option. It is easy to see that we want to use the largest possible value of $$$i$$$, because we are going to keep everything before index $$$i$$$ the same, and increase the value at index $$$i$$$. Let $$$1 \lt k \lt n$$$ denote the index of the last local maximum; that is, $$$k$$$ is the largest integer satisfying $$$p_k \gt p_{k-1}, p_{k+1}$$$. Then we claim that $$$i=k-1$$$ is optimal.

First, we show that it is valid. Indeed, the subarray $$$p[i, i+2] = p[k-1, k+1]$$$ is clearly valid. Next, we show that there is no larger valid choice of $$$i$$$. Notice that $$$p[k, n]$$$ is first decreasing, then increasing (possibly over an empty subarray). If we choose $$$i \lt j$$$ contained in the decreasing portion, then $$$p_i$$$ will be the maximum of $$$p[i, j]$$$. If we choose $$$i \lt j$$$ in the increasing portion, then $$$p_j$$$ will be the maximum of $$$p[i, j]$$$. Finally, if we choose $$$i \lt j$$$ that crosses from the decreasing to the increasing portion, then $$$\max(p_i, p_j)$$$ is the maximum of $$$p[i, j]$$$. Therefore, no subarray that uses $$$i \geq k$$$ can possibly be valid.

We conclude that we must choose $$$i = k-1$$$. Notice that identical reasoning to the above proof shows that if there is no local maximum, then no valid $$$q$$$ exists, so we may output $$$-1$$$. We further observe that the value of $$$k$$$, if it exists, can be determined in $$$n-1$$$ queries of adjacent values.

Now, we want to choose the value of $$$j$$$. It is easy to see that we want to choose the largest possible value of $$$j$$$, because it gives us strictly more options of how to rearrange the subarray. Since $$$p[k, n]$$$ is decreasing then (possibly) increasing, it suffices to find the first value larger than $$$p_k$$$, then we will choose the subarray to end right before that value. If no such value exists, we can choose $$$j = n$$$.

However, we do not have to explicitly find the value of $$$j$$$. In fact, it suffices to pretend that $$$j = n$$$, and then using the construction from earlier, it will naturally follow that everything larger than the actual value of $$$j$$$ will remain untouched, since that portion of $$$p$$$ is already increasing. So now, we simply have to sort the values in $$$p[i, n]$$$, then move the one that comes directly after $$$p_i$$$ to the front.

Notice that we can split this subarray into three monotonic sections; furthermore, we know where the cutoffs for these sections are, since we have queried all adjacent values before. We can sort by finding the next minimum of the subarray one by one. We know that the next minimum must be the next minimum of one of the three sections, and since they are monotonic, we can track these with three pointers. We can find which of these three values is the smallest using two queries. In total, we sort the subarray using at most $$$2(n-1)$$$ queries. We can then move the value directly after $$$p_i$$$ to the spot $$$q_i$$$ without any additional queries.

This solves the problem using at most $$$3n$$$ queries, as desired.

#include <bits/stdc++.h>

using namespace std;

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

    auto ask = [&](int i, int j) {
        cout << "? " << i << " " << j << endl;

        int ans;
        cin >> ans;
        return ans;
    };

    int j = -1;
    vector<int> val(n + 2); val[n] = 1;
    for(int i = n - 1; i; i--) {
        val[i] = ask(i, i + 1);
        if(val[i] && !val[i + 1]) {
            j = i;
            break;
        }
    }
    if(j == -1) {
        cout << "! " << -1 << endl;
        return;
    }

    // Need to sort [j + 1, n]
    int k = j + 1;
    while(!val[k + 1]) k++;

    // [j + 1, k] - decreasing
    // [k + 1, n] - increasing
    vector<int> order;
    int l = k, r = k + 1;
    while(l > j && r <= n) {
        if(ask(l, r)) order.push_back(l--);
        else order.push_back(r++);
    }
    while(l > j) order.push_back(l--);
    while(r <= n) order.push_back(r++);

    l = 0, r = order.size() - 1;
    while(l <= r) {
        int m = l + r >> 1;
        if(ask(j, order[m])) r = m - 1;
        else l = m + 1;
    }
    assert(l < order.size());

    vector<int> res(n + 1);
    iota(res.begin(), res.end(), 0);
    res[j] = order[l];
    order[l] = j;
    for(int i = j + 1; i <= n; i++) {
        res[i] = order[i - j - 1];
    }

    res.erase(res.begin());
    cout << "! "; for(auto i : res) cout << i << " "; cout << endl;
}

signed main() {
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Why isn't $$$P(v)$$$ always $$$n - 1$$$? Specifically, when can we delete vertex $$$n - 1$$$?

Since each tree (with $$$n \ge 2$$$) has at least two leaves, $$$n - 1$$$ can be deleted only if $$$n - 1$$$ and $$$n$$$ are the only leaves. This means that there's just a single path from $$$n$$$ to $$$n - 1$$$. In this case it's obvious that the second vertex on the path will be left at the end. Therefore, $$$P(v)$$$ is always the second vertex on the path from $$$n$$$ to $$$n - 1$$$.

So now we just have to count the number of ways to connect the tree satisfying these conditions. The easiest case is when $$$n$$$ and $$$n - 1$$$ are in the same component, then the Prufer vertex is fixed, so making the forest a tree doesn't change it.

Let's assume that $$$n$$$ and $$$v$$$ are already connected, because if not, we have to connect them with an edge, and we can update all the needed values dynamically.

We have to connect the tree so that $$$n - 1$$$ is in the subtree of $$$v$$$ (when rooted at $$$n$$$).

Let $$$C$$$ be the set of vertices in the component of $$$n$$$. Notice that since all vertices in $$$C$$$ are indistinguishable, the component with $$$n - 1$$$ will be attached to the component of $$$n$$$ to each vertex in $$$C$$$ in the same number of final trees.

Let $$$k$$$ be the size of the subtree of $$$v$$$. Then in $$$\dfrac{k}{|C|}$$$ of all trees $$$n - 1$$$ will be connected to $$$n$$$ through a subtree of $$$v$$$.

Therefore, we just need to maintain the total number of ways to complete the tree and after adding edges from $$$n$$$ to $$$v$$$, and multiply that value by $$$\dfrac{k}{|C|}$$$ to solve the problem.

Time complexity: $$$O(n)$$$ or $$$O(n \log n)$$$.

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

// Removed Mint template for better readability

vector<Mint> get(vector<vector<int>> g) {
    int n = g.size() - 1;

    vector<int> comp(n + 1, -1), dp(n + 1, 1), parent(n + 1), sizes(n);
    int k = 0;
    function<void(int, int)> dfs = [&](int v, int p) {
        comp[v] = k; sizes[k]++;

        for(auto to : g[v]) {
            if(to == p) continue;

            parent[to] = v;
            dfs(to, v);
            dp[v] += dp[to];
        }
    };
    for(int v = n; v; v--) {
        if(comp[v] == -1) {
            dfs(v, 0);
            k++;
        }
    }

    vector<int> sz(n + 1);
    for(int v = 1; v <= n; v++) sz[v] = sizes[comp[v]];

    vector<Mint> inv(n + 1); inv[1] = 1;
    for(int i = 2; i <= n; i++) {
        inv[i] = mod - inv[mod % i] * (mod / i);
    }

    vector<Mint> ans(n);
    Mint p = 1;
    for(int i = 0; i < k; i++) p *= sizes[i];

    vector<Mint> n_power(n + 1);
    n_power[0] = 1; for(int i = 1; i <= n; i++) n_power[i] = n_power[i - 1] * n;

    auto n_pow = [&](int k) {
        if(k >= 0) return n_power[k];
        else if(k == -1) return inv[n];
        else assert(0);
    };

    if(comp[n] == comp[n - 1]) {
        // If n and n - 1 are already in one component P(T) is determined
        int v = n - 1;
        while(parent[v] != n) v = parent[v];

        ans[v] = p * n_pow(k - 2);
    }
    else {
        for(int v = 1; v <= n - 1; v++) {
            if(comp[v] == comp[n]) {
                // v and n have to be connected
                if(parent[v] != n) continue;

                ans[v] = dp[v] * p * inv[sz[n]] * n_pow(k - 2);
            }
            else if(comp[v] == comp[n - 1]) {
                // Just connect v and n
                ans[v] = p * inv[sz[n]] * inv[sz[n - 1]] * (sz[n] + sz[n - 1]) * n_pow(k - 3);
            }
            else {
                // Connect v and n and same as first case
                ans[v] = sz[v] * p * inv[sz[n]] * inv[sz[v]] * n_pow(k - 3);
            }
        }
    }

    return ans;
}

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

    vector<vector<int>> g(n + 1);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v); g[v].push_back(u);
    }

    vector<Mint> ans = get(g);
    for(int v = 1; v < n; v++) cout << ans[v] << ' '; cout << endl;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Notice that $$$1$$$ and $$$n$$$ can never be medians, so $$$f(p)$$$ has to be a permutation of $$${ 2, \ldots, n }$$$.

Suppose that we have 5 consecutive elements $$$[p_1, p_2, p_3, p_4, p_5]$$$, and $$$p_1 \lt p_3 \gt p_5$$$. WLOG, assume that $$$p_2 \lt p_4$$$. It turns out there's a very tight condition for this case to not have duplicates. Mainly, $$$p_3$$$ has to be the largest element.

Notice that since $$$p_3$$$ is the largest element among all $$$3$$$ subarrays in which it takes part in, $$$p_3$$$ cannot appear in $$$f(p)$$$. Therefore, an important observation is: if $$$p_{i - 2} \lt p_i \gt p_{i + 2}$$$, then $$$p_i = n$$$. Similarly, if $$$p_{i - 2} \gt p_i \lt p_{i + 2}$$$, then $$$p_i = 1$$$.

From this we can see that all indices with the same parity are almost monotonic. But how do even and odd indices interact with each other?

Let's consider another case: $$$[p_1, p_2, p_3, p_4]$$$, $$$p_1 \lt p_3$$$ and $$$p_2 \gt p_4$$$ (odd is increasing, even is decreasing). We can see that this case also has a simple structure. Mainly, if we bruteforce (to not consider a lot of cases) all valid permutations of size $$$4$$$ that satisfy the two inequalities above, we'll get only two solutions: $$$[1, 4, 2, 3]$$$ and $$$[3, 2, 4, 1]$$$. This means that either all even indices have values greater than all odd indices, or vice versa.

The two conditions we found are actually already sufficient, and it's very easy to prove this.

Suppose $$$f(p)_i = f(p)_j$$$ with $$$i \lt j$$$, so $$$p$$$ is invalid. Notice that for this to happen $$$[i, i + 2]$$$ and $$$[j, j + 2]$$$ have to both include the same value in $$$p$$$, so $$$[i, i + 2]$$$ and $$$[j, j + 2]$$$ have to intersect, so $$$i + 2 \ge j$$$, or $$$j - i \le 2$$$. Therefore, it is sufficient to check that there are no "bad" subarrays $$$[i, i + 4]$$$, and if all subarrays of size $$$5$$$ are valid in $$$p$$$, $$$p$$$ is valid as well.

Using this and our two conditions above we can just check all permutations of size $$$5$$$ and verify that they are sufficient.

So now we only have to understand how to count. The conditions we have are actually pretty restrictive.

WLOG, assume that $$$1$$$ is located earlier than $$$n$$$.

First consider the case where $$$pos_1$$$ and $$$pos_n$$$ have the different parity.

Consider the picture below. Each arrow denotes that the element should be smaller than the element arrow points to. Let's see how even and odd indices compare to each other.

Look at $$$i = 2$$$. We have $$$p_2 \gt p_4$$$ and $$$p_3 \lt p_5$$$, which is the second condition we had. Since $$$p_4 = 1$$$, we must have $$$p_4 \lt p_2 \lt p_3 \lt p_5$$$. For $$$i = 1$$$ the same thing holds, and since we already know that $$$p_3 \gt p_2$$$ (and all odd indices in this case must have a larger element than even indices), we must have $$$p_4 \lt p_2 \lt p_1 \lt p_3 \lt p_5$$$.

The same thing happens after $$$n$$$ on the right side, we must have: $$$p_{10} \lt p_{12} \lt p_{13} \lt p_{11} \lt p_9$$$, so essentially can add two new (purple) arrows to the picture:

And after some recoloring, we can see that the when $$$1$$$ and $$$n$$$ are located on different parities, there must be two chains of values:

After applying the same logic, we get a similar situation when $$$1$$$ and $$$n$$$ are located on the same parity:

From this we can see that in all cases there are at most two increasing chains (dark-red and orange on the two pictures above).

Since we know the positions of $$$1$$$ and $$$n$$$, the problem now transformed into: given two chains of increasing values, we have to count the number of ways to put all values $$$1, 2, \ldots, n$$$ into the chains with some values already being placed.

Suppose we have two chains $$$a$$$ and $$$b$$$ with sizes $$$k$$$ and $$$l$$$, and we know that some $$$a_i = x$$$. Notice that this means that $$$i - 1$$$ of the $$$x - 1$$$ elements before $$$x$$$ have to be in $$$a$$$, and all the others must be in $$$b$$$. This means that we can go through all placed elements and count the number of ways to position the unplaced ones using binomial coefficients. You can read the code for better understanding.

Time complexity: $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

const long long mod = 998244353;
const int MAX = 2e5 + 42;

// Mint template omitted for readability

Mint fact[MAX], inv[MAX];

Mint C(int n, int k) {
    if(n < k || k < 0) return 0;
    return fact[n] * inv[k] * inv[n - k];
}

Mint get(vector<int> p) {
    int n = p.size();

    int pos_1 = -1, pos_n = -1;
    for(int i = 0; i < n; i++) {
        if(p[i] == 1) pos_1 = i;
        if(p[i] == n) pos_n = i;
    }
    assert(pos_1 != -1);
    assert(pos_n != -1);

    if(pos_1 > pos_n) {
        reverse(p.begin(), p.end());
        pos_1 = n - 1 - pos_1;
        pos_n = n - 1 - pos_n;
    }

    vector<vector<int>> g(n + 1);
    if(pos_1 % 2 == pos_n % 2) {
        for(int i = (pos_1 & 1 ^ 1); i < n; i += 2) {
            if(i >= 2) g[i - 2].push_back(i);
        }
        for(int i = pos_1 - 2; i >= 0; i -= 2) {
            g[i + 2].push_back(i);
        }
        for(int i = pos_1 + 2; i <= pos_n; i += 2) {
            g[i - 2].push_back(i);
        }
        for(int i = pos_n + 2; i < n; i += 2) {
            g[i].push_back(i - 2);
        }
    }
    else {
        for(int i = pos_1 - 2; i >= 0; i -= 2) {
            g[i + 2].push_back(i);
        }
        for(int i = pos_1 + 2; i < n; i += 2) {
            g[i - 2].push_back(i);
        }

        for(int i = pos_n - 2; i >= 0; i -= 2) {
            g[i].push_back(i + 2);
        }
        for(int i = pos_n + 2; i < n; i += 2) {
            g[i].push_back(i - 2);
        }
    }

    if(pos_1 != 0) {
        if(pos_1 % 2 == 0) g[0].push_back(1);
        if(pos_1 % 2 == 1) g[1].push_back(0);
    }
    if(pos_n != 0) {
        if(pos_n % 2 == (n - 1) % 2) g[n - 2].push_back(n - 1);
        if(pos_n % 2 != (n - 1) % 2) g[n - 1].push_back(n - 2);
    }

    g[pos_1].clear();
    for(int i = 0; i < n; i++) {
        if(i == pos_1 || i == pos_n) continue;
        assert(g[i].size() == 1);
        if(g[i][0] == pos_n) g[i].clear();
    }

    vector<int> in_degree(n);
    for(int v = 0; v < n; v++) {
        for(auto to : g[v]) in_degree[to]++;
    }

    vector<pair<int, int>> pos(n + 1);
    int t = 0, cnt = 0;
    for(int i = 0; i < n; i++) {
        if(i == pos_1 || i == pos_n || in_degree[i] > 0) continue;

        t++;
        cnt = 0;
        if(t == 1) pos[1] = {t, cnt++};
        int j = i;
        while(1) {
            pos[p[j]] = {t, cnt++};

            if(g[j].empty()) break;
            j = g[j][0];
        }
    }
    pos[n] = {t, cnt};

    Mint ans = 1;
    for(int i = 1; i < n; i++) {
        int j = i + 1;
        while(pos[j].first == 0) j++;

        auto [ti, ci] = pos[i]; ci++;
        auto [tj, cj] = pos[j];
        if(ti == 2) ci = i - ci;
        if(tj == 2) cj = j - 1 - cj;

        // At i we have ci in first, at j - 1 we have cj
        // Choose cj - ci from j - i - 1
        ans *= C(j - i - 1, cj - ci);
        i = j - 1;
    }

    return ans;
}

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for(auto &i : p) {
        cin >> i;
    }

    Mint ans = get(p);
    cout << ans << '\n';
}

signed main() {
    fact[0] = 1; for(int i = 1; i < MAX; i++) fact[i] = fact[i - 1] * i;
    inv[MAX - 1] = 1 / fact[MAX - 1];
    for(int i = MAX - 1; i; i--) inv[i - 1] = inv[i] * i; assert(inv[0] == 1);
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

A few notations:

• $$$S(x, y, k) = {(x + i) \oplus (y + j) \mid 0 \le i \lt k,\ 0 \le j \lt k}$$$.
• $$$S(x, y, k, l) = {(x + i) \oplus (y + j) \mid 0 \le i \lt k,\ 0 \le j \lt l}$$$.
• $$$[l, r] \oplus x = {i \oplus x \mid l \le i \le r}$$$.
• $$$[l_1, r_1] * [l_2, r_2] = {i \oplus j \mid l_1 \le i \le r_1,\ l_2 \le j \le r_2}$$$ (We'll call this the XOR Cartesian product).

Let's try to find a formula for a general $$$S(x, y, k)$$$. Consider the simplified case $$$x = y$$$.

If $$$x = y = 0$$$, we can achieve every XOR value up to the maximum possible XOR. Let $$$p$$$ be the smallest integer such that $$$2^p \ge k$$$. Then $$$S(0, 0, k) = [0,\ 2^p - 1]$$$.

When $$$x \neq y$$$, notice that $$$x$$$ and $$$x + k - 1$$$ share some common prefix of bits. Let its length be $$$L$$$. That prefix is present in all $$$x + i$$$ and $$$x + j$$$, so it cancels out in XOR. Therefore, we can zero out the top $$$L$$$ bits and assume $$$\lfloor \log_2 x \rfloor \neq \lfloor \log_2 (x + k - 1) \rfloor$$$.

Let $$$p = \lfloor \log_2 (x + k - 1)\rfloor$$$ and $$$P = 2^p$$$. Then $$$x$$$ does not have the bit $$$P$$$ set, and we can split: - $$$[x,\ P - 1]$$$ - $$$[P,\ x + k - 1]$$$

Now write $$$S(x, x, k)$$$ as the union of XOR-products of these two ranges (there are 3 distinct ones, since cross terms are symmetric).

Define $$$a = (P - 1) - x, \quad b = (x + k - 1) - P$$$.

Product A: $$$[P,\ x + k - 1] * [P,\ x + k - 1]$$$. All numbers in $$$[P,\ x + k - 1]$$$ have the bit $$$P$$$ set, so it cancels in XOR. After removing that bit: $$$ [P,\ x + k - 1] * [P,\ x + k - 1] = S(0, 0, b + 1)$$$. (Here $$$b + 1 = (x + k - 1) - P + 1 = x + k - P$$$.)

Product B: $$$[x,\ P - 1] * [x,\ P - 1]$$$. This is similar to the $$$S(0, 0, \cdot)$$$ case but taken from the other side. Replace each $$$t \in [x,\ P - 1]$$$ with $$$t \oplus (P - 1)$$$, which equals to $$$(P - 1) - t$$$. Since we XOR both sides, the set of XORs does not change, and we get: $$$[x,\ P - 1] * [x,\ P - 1] = S(0, 0, a + 1)$$$ (here $$$a + 1 = (P - 1 - x) + 1 = P - x$$$).

Product C, the hardest case: $$$[x,\ P - 1] * [P,\ x + k - 1]$$$ Apply the same transforms:

• $$$[x,\ P - 1] \to [0,\ a]$$$

• $$$[P,\ x + k - 1] \to [0,\ b]$$$

But now the “removed masks” do not cancel out, so at the end we must XOR by $$$(P - 1) \oplus P = 2^{p + 1} - 1$$$.

So: $$$[x,\ P - 1] * [P,\ x + k - 1] = S(0, 0, a + 1, b + 1)\ \oplus\ (2^{p + 1} - 1)$$$.

Let's understand how to find $$$S(0, 0, k, l)$$$. Claim: $$$S(0, 0, k, l)$$$ is a single interval, or $$$S(0, 0, k, l) = [0, f(k - 1, l - 1)]$$$, where $$$f(n, m)$$$ is the largest XOR of $$$0 \le i \le n$$$ and $$$0 \le j \le m$$$.

It's not hard to compute $$$f(n, m)$$$ in general.

Using this, Product C becomes an interval: $$$S(0,0,a + 1,b + 1)\oplus (2^{p + 1} - 1) = [0,\ f(a, b)]\ \oplus\ (2^{p + 1} - 1) = [2^{p + 1} - 1 - f(a, b),\ 2^{p + 1} - 1]$$$.

So, combine the three parts: $$$S(x, x, k) = S(0, 0, a + 1)\ \cup\ S(0, 0, b + 1)\ \cup\ [2^{p + 1} - 1 - f(a, b),\ 2^{p + 1} - 1]$$$.

This can be simplified to: $$$S(x, x, k) = S(0, 0, \max(a + 1,\ b + 1)) \ \cup\ [2^{p + 1} - 1 - f(a, b),\ 2^{p + 1} - 1]$$$.

Now handle $$$x \ne y$$$ similarly. First assume that: $$$x$$$ and $$$x + k - 1$$$ have no common non-zero prefix bits (after stripping common prefix as before, though in this case it's not obvious that this will not change the set, but we'll handle this later), and similarly for $$$y$$$.

Let: $$$p_x = \lfloor \log_2(x + k - 1)\rfloor,\quad P_x = 2^{p_x}$$$, $$$p_y = \lfloor \log_2(y + k - 1)\rfloor,\quad P_y = 2^{p_y}$$$.

Split into four intervals: - $$$[x,\ P_x - 1]$$$, $$$[P_x,\ x + k - 1]$$$ - $$$[y,\ P_y - 1]$$$, $$$[P_y,\ y + k - 1]$$$

Define $$$a = (P_x - 1) - x,\quad b=(x + k - 1) - P_x$$$, $$$c = (P_y - 1) - y,\quad d=(y + k - 1) - P_y$$$.

Now consider the four products:

1. $$$I_1 = [x, P_x - 1] * [y, P_y - 1] = [0, f(a, c)] \oplus (P_x - 1) \oplus (P_y - 1)$$$

2. $$$I_2 = [P_x, x + k - 1] * [P_y, y + k - 1] = [0, f(b, d)] \oplus P_x \oplus P_y$$$

3. $$$I_3 = [x, P_x - 1] * [P_y, y + k - 1] = [0, f(a, d)] \oplus (P_x - 1) \oplus P_y$$$

4. $$$I_4 = [P_x, x + k - 1] * [y, P_y - 1] = [0, f(b, c)] \oplus P_x \oplus (P_y - 1)$$$

Notice that the $$$P_x = P_y = P$$$ case is trivial, we already almost solved it, and by the same reasoning $$$S(x, y, k) = [0, \max(f(b, d), f(a, c)] \cup [2P - 1 - max(f(a, d), f(b, c), 2P - 1]$$$ in this case.

Now WLOG assume $$$P_x \lt P_y$$$. We have $$$a + b = c + d = k - 2$$$. Notice that $$$a, b \lt P_x$$$ (since $$$a = P_x - 1 - x$$$ and $$$P_x + b \lt 2P_x$$$). Also notice that $$$c, d \lt 2P_x$$$, since $$$\max(a, b) \le \dfrac{k}{2} \lt P_x$$$, so $$$k \lt 2P_x$$$ and $$$c + d = k - 2$$$.

Consider $$$I_2 = [0, f(b, d)] \oplus P_x \oplus P_y$$$. Since $$$P_x \lt P_y$$$, write $$$P_x \oplus P_y = P_x + P_y$$$. Also $$$f(b, d) \lt 2P_x$$$.

• If $$$f(b, d) \lt P_x$$$, then $$$I_2 = [P_x + P_y,\ P_x + P_y + f(b, d)]$$$

• If $$$f(b, d) \ge P_x$$$, then $$$[0, f(b, d)]$$$ contains $$$P_x$$$, and we get: $$$I_2 = [P_y,\ P_y + (f(b, d) - P_x)]\ \cup\ [P_x + P_y,\ P_y + 2P_x - 1]$$$.

Now consider $$$I_3 = [0, f(a, d)] \oplus (P_x - 1) \oplus P_y$$$. XORing by $$$(P_x - 1)$$$ is just a reversal inside $$$[0, P_x - 1]$$$ and separately inside $$$[P_x, 2P_x - 1]$$$.

• If $$$f(a, d) \lt P_x$$$, then $$$I_3 = [P_y + (P_x - 1 - f(a, d)),\ P_y + (P_x - 1)]$$$

• If $$$f(a, d) \ge P_x$$$, then $$$I_3 = [P_y,\ P_y + (P_x - 1)]\ \cup\ [P_y + (2P_x - 1 - f(a, d)),\ P_y + (2P_x - 1)]$$$

An important observation is that if $$$d \ge P_x$$$, then $$$f(a, d), f(b, d) \ge P_x$$$, and $$$f(a, d), f(b, d) \lt P_x$$$ otherwise, since $$$a, b \lt P_x$$$. So:

• If $$$d \ge P_x$$$, then $$$I_2 \cup I_3 = [P_y,\ P_y + 2P_x - 1]$$$

• If $$$d \lt P_x$$$, then $$$I_2 \cup I_3 = [P_y + P_x - 1 - f(a, d),\ P_y + P_x + f(b, d)]$$$

So in all cases, $$$I_2 \cup I_3$$$ is exactly one interval, and its length is: $$$|I_2 \cup I_3| = \min\left( f(a, d) + f(b, d) + 2,\ 2P_x \right)$$$.

The other two intervals are similar, except now we XOR by $$$(P_y - 1)$$$ instead of $$$P_y$$$. We can rewrite this as $$$(P_x - 1) \oplus (P_y - 1) = (P_x \oplus P_y) \oplus (P_x - 1) \oplus (P_y - 1) = (P_y - 2P_x) \oplus P_x$$$.

From this we can get a similar result:

• If $$$c \ge P_x$$$, $$$I_1 \cup I_4 = [P_y - 2P_x,\ P_y - 1]$$$

• If $$$c \lt P_x$$$, $$$I_1 \cup I_4 = [P_y - P_x - 1 - f(b, c),\ P_y - P_x + f(a, c)]$$$

So again we get exactly one interval, and $$$|I_1 \cup I_4| = \min\left( f(a, c) + f(b, c) + 2,\ 2P_x \right)$$$.

Notice that the two cases never intersect:

• $$$I_1 \cup I_4$$$ is inside $$$[P_y - 2P_x,\ P_y - 1]$$$.

• $$$I_2 \cup I_3$$$ is inside $$$[P_y,\ P_y + 2P_x - 1]$$$.

Therefore $$$|S(x, y, k)| = |I_1 \cup I_4| + |I_2 \cup I_3| = \min\left(f(a, c) + f(b, c) + 2,\ 2P_x\right)\ +\ \min\left(f(a, d) + f(b, d) + 2,\ 2P_x\right)$$$

Remember that we had assumed that $$$x$$$ and $$$x + k - 1$$$ had no common non-zero prefix bits (and same for $$$y$$$). If they do, let $$$X$$$ be that common prefix value for $$$x$$$ and $$$Y$$$ for $$$y$$$. Then every element of $$$S(x, y, k)$$$ is XORed by $$$X \oplus Y$$$.

However, notice that $$$X, Y \ge 2P_x$$$, since $$$P_x$$$ is the first bit that differs in $$$x$$$ and $$$x + k - 1$$$, and if we XOR by a bit after $$$P_x$$$ the values will just shift, but the size won't change. So when $$$x$$$ and $$$x + k - 1$$$ have a common prefix, we can just get rid of it without changing the size of $$$S$$$.

Now we can solve the original problem, where $$$x$$$ is fixed. If $$$P_x = P_y$$$ the size of always smaller than when not, so we only have to consider the case when $$$P_x \neq P_y$$$. In fact, it is always optimal to have $$$P_y \gt P_x$$$, because having a smaller $$$P_y$$$ will trigger the $$$2P_x$$$ part of the formula.

We have $$$a$$$ and $$$b$$$ fixed from $$$x$$$, so the formula we need to optimize is: $$$\min\left(f(a, c) + f(b, c) + 2,\ 2P_x\right)\ +\ \min\left(f(a, k - 2 - c) + f(b, k - 2 - c) + 2,\ 2P_x\right)$$$ over all $$$0 \le c \le k - 2$$$. We can easily do that with digit dp in $$$O(\log k)$$$ with a constant factor of around $$$100$$$, which solves the problem.

#include <bits/stdc++.h>

using namespace std;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }

const long long inf = 4.1e18;
const int LG = 61;

long long get_different(long long power, long long k, long long A) {
    long long B = k - A;
    vector<vector<long long>> dp(2, vector<long long>(16, -inf));
    dp[0][0] = 0;

    int cnt_states = 0;
    for(int L = LG - 1; ~L; L--) {
        vector<vector<long long>> ndp(2, vector<long long>(16, -inf));

        for(int C = 0; C < 2; C++) {
            for(int cd = 0; cd < 4; cd++) {
                int a = A >> L & 1;
                int b = B >> L & 1;
                int c = cd >> 1;
                int d = cd & 1;

                int new_C = (k >> L & 1) ^ c ^ d;
                if((new_C + c + d >= 2) != C) continue;

                for(int mask = 0; mask < 16; mask++) {
                    if(dp[C][mask] < 0) continue;

                    // ac - 0, ad - 1, bc - 2, bd - 3
                    int new_mask = mask;
                    long long add = 0;

                    if((1ll << L) >= power && c) add += (2ll << L) - 2, new_mask |= (1 << 0) | (1 << 2);
                    if((1ll << L) >= power && d) add += (2ll << L) - 2, new_mask |= (1 << 1) | (1 << 3);

                    if((new_mask >> 0 & 1 ^ 1) && (a & c)) add += (1ll << L + 1) - 1, new_mask |= 1 << 0;
                    if((new_mask >> 1 & 1 ^ 1) && (a & d)) add += (1ll << L + 1) - 1, new_mask |= 1 << 1;
                    if((new_mask >> 2 & 1 ^ 1) && (b & c)) add += (1ll << L + 1) - 1, new_mask |= 1 << 2;
                    if((new_mask >> 3 & 1 ^ 1) && (b & d)) add += (1ll << L + 1) - 1, new_mask |= 1 << 3;

                    if(new_mask >> 0 & 1 ^ 1) add += ((long long) (a | c)) << L;
                    if(new_mask >> 1 & 1 ^ 1) add += ((long long) (a | d)) << L;
                    if(new_mask >> 2 & 1 ^ 1) add += ((long long) (b | c)) << L;
                    if(new_mask >> 3 & 1 ^ 1) add += ((long long) (b | d)) << L;

                    cnt_states++;
                    long long cand = dp[C][mask] + add;
                    umax(ndp[new_C][new_mask], cand);
                }
            }
        }

        dp = ndp;
    }

    long long best = -inf;
    for(int mask = 0; mask < 16; mask++) {
        umax(best, dp[0][mask]);
    }
    return best + 4;
}

long long get(long long x, long long k) {
    if(k == 1) return 1;

    int px = __lg(x ^ x + k - 1);
    long long Px = 1ll << px;
    x &= Px * 2 - 1;

    long long a = Px - 1 - x;
    return get_different(Px, k - 2, a);
}

void solve() {
    long long k, x;
    cin >> x >> k;

    cout << get(x, k) << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First let's find an easy way to calculate the determinant of a fixed $$$A$$$. We can easily see that $$$\operatorname{det}(A) \in [-1, 0, 1]$$$ for any $$$A$$$.

Let's first of all understand when it is $$$0$$$, so in other words we need to find if the determinant is even.

Notice that replacing each row with its difference array is a linear transformation, because we can set $$$a_{i, j} = a_{i, j} - a_{i, j - 1}$$$ for all $$$j$$$ simultaneously, and do that for all $$$i$$$ from the end.

Therefore, let's add an extra column so that the matrix is $$$n$$$ by $$$n + 1$$$ now, and replace each row with its difference array. Now every row has exactly one $$$1$$$ and exactly one $$$-1$$$, or exactly two $$$1$$$'s when looked at $$$\operatorname{mod} 2$$$.

So we have $$$n$$$ binary strings of size $$$n + 1$$$ with two $$$1$$$'s in each string and we want to determine if they are linearly independent.

The solution to this is known, and the strings are linearly independent iff there are no cycles in a graph with $$$n + 1$$$ vertices and $$$n$$$ edges $$$(x_i, y_i)$$$.

Therefore, the determinant is $$$0$$$ iff there is a cycle in a graph with $$$n + 1$$$ vertices and $$$n$$$ edges $$$(l_i, r_i + 1$$$) (since each row got replaced with a difference array, so the last $$$1$$$ shifted to a $$$-1$$$ in the next index).

If the graph is a tree, the determinant is $$$1$$$ or $$$-1$$$. Let's learn to determine which one it is.

Notice that if $$$l_i = r_i$$$ for all $$$i$$$, the determinant is the parity of a permutation, so it clearly can't be simplified beyond that, so let's try to get it down to that.

Let's try to transform the matrix into a permutation. Consider the following matrix:

The tree of this matrix looks like this:

Denote $$$p_v$$$ as the parent of vertex $$$v$$$, $$$f(v)$$$ as the index of a row with $$$v$$$ and $$$p_v$$$. If $$$p_v = n + 1$$$ holds for all $$$v$$$, $$$p_v$$$ has a $$$-1$$$ and $$$v$$$ has $$$1$$$ at $$$f(v)$$$-th row, we are simply in a case of a permutation that was discussed earlier, so let's transform the matrix into that.

Let's make it so $$$p_v$$$ has a $$$-1$$$ and $$$v$$$ has $$$1$$$, so multiply $$$f(v)$$$-th row by $$$-1$$$ if $$$p_v \lt v$$$:

Now we can iteratively move $$$p_v \neq n + 1$$$ to $$$p_{p_v}$$$ by adding $$$f(p_v)$$$ to $$$f(v)$$$. For example, in the picture above for $$$v = 4$$$ we add $$$i = 1$$$ to $$$i = 4$$$ and get a new tree:

This way we can transform the matrix to have $$$p_v = n + 1$$$:

At the end we end up with a $$$p_v = n + 1$$$ for all $$$v$$$, and since the last column doesn't actually exist in the matrix, the matrix is just a permutation, and we can find its sign.

Notice an imporant fact: during our operations $$$f(v)$$$ didn't change, only $$$p_v$$$ did, so at the end we will always end up with the permutation $$$q$$$ of size $$$n$$$ with $$$q_{f(v)} = v$$$.

To sum it up, to find the sign of $$$A$$$:

Let $$$k$$$ be the number of $$$v$$$ that $$$p_v \lt v$$$, and let $$$q$$$ be the permutation with $$$q_{f(v)} = v$$$. Then $$$\operatorname{det}(A) = (-1)^k \cdot \operatorname{sgn}(q)$$$.

Now let's use this formula to solve the original problem. We have to make $$$A$$$ has a determinant of $$$1$$$. Obviously, if it's already $$$1$$$, the answer is $$$0$$$.

Let's first solve the case when it's $$$-1$$$. Notice an important fact: if we modify two rows, we can simply swap them, and that negates the determinant.

So the upperbound on the answer is the sum of two smallest values of $$$a_i$$$. We now simply have to determine the smallest cost of an edge that can negate the determinant on it's own.

Root the tree at $$$n + 1$$$ again, we delete the $$$i$$$-th edge $$$v \rightarrow p_v$$$, and replace it with an edge $$$x \rightarrow y$$$, where $$$x$$$ is a direct child of $$$v$$$. Assume that $$$f(x) = j$$$. How does the determinant change?

Notice that besides $$$i$$$, only the direction of edge $$$j$$$ changes. In particular, the edge $$$x \rightarrow v$$$ changes to $$$v \rightarrow x$$$, and $$$i$$$-th edge is now $$$x \rightarrow y$$$.

How does $$$q$$$ change? Before the operation, $$$q_i = v$$$ and $$$q_j = x$$$, now $$$q_i = x$$$ and $$$q_j = v$$$, so it swaps $$$q_i$$$ and $$$q_j$$$, which negates the sign. Additionally, since $$$j$$$-th edge was reversed, the value of $$$-1^{[x \gt v]}$$$ changed to $$$-1^{[v \gt x]}$$$, so this part was negated as well.

Therefore, the only change in determinant is: $$$-1^{[v \gt p_v] + [x \gt y]}$$$. We can iteratively apply this to get the same result for when $$$x$$$ is not a child of $$$v$$$.

Therefore, if we replace $$$v \rightarrow p_v$$$ with $$$x \rightarrow y$$$, where $$$x$$$ is in the subtree of $$$v$$$ and $$$y$$$ is outside of subtree of $$$v$$$, the determinant is multiplied by $$$-1^{[v \gt p_v] + [x \gt y]}$$$.

This means that we can change the sign of determinant if the values of $$$[v \gt p_v]$$$ and $$$[x \gt y]$$$ are different.

Let $$$\max_v$$$ be the largest value in the subtree of $$$v$$$, and $$$\min_v$$$ the smallest value outside of the subtree of $$$v$$$. Then we can use the edge $$$v \rightarrow p_v$$$ to change the sign iff $$$\max_v \gt \min_v$$$, because if we choose $$$x = v$$$, $$$y = n + 1$$$, the sign is going to be different compared to when we choose $$$x = \max_v$$$, $$$y = \min_v$$$.

We can use this to determine if we can change the sign with an edge $$$i$$$ and find the smallest cost of one which we can use. This solves the case when the determinant is $$$-1$$$.

Now the only thing left is to solve when the determinant is $$$0$$$. Our graph is not a tree now.

Notice that if there are at least $$$3$$$ components, we have to change at at least $$$2$$$ edges, so we don't have to worry about the sign, since we can swap two edges if needed like we did in the previous case.

So we simply have to make the graph a tree while changing a subset of edges with the smallest total cost, which is precisly the MST problem (slightly modified).

The only case left is when the graph consists of two components. We can actually use the exact same observations as in the $$$\operatorname{det}(A) = -1$$$. There's a cycle, we have to remove one edge from it and connect the components. We can also change two edges, but at least one of them has to be in the cycle.

In the first case we have to check if the smallest value in the component with $$$n + 1$$$ is smaller than the largest value in the other component, and if so, we can choose any edge on the cycle. Otherwise, we have to apply the same logic as we did earlier.

Final time complexity: $$$O(n \log n)$$$ due to sorting for finding MST.

#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18;

struct DSU {
    int n;
    vector<int> p, siz;
    int comp;

    DSU(int N) {
        n = N - 1;
        comp = 0;
        p = vector<int>(n + 1);
        siz = vector<int>(n + 1);
    };

    void create(int x) {
        p[x] = x;
        siz[x] = 1;
        comp++;
    }

    void init() {
        comp = 0;
        for(int v = 1; v <= n; v++) create(v);
    }

    int get(int x) {
        return p[x] = (p[x] == x? x : get(p[x]));
    }

    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if(x == y) return 0;
        if(siz[x] < siz[y]) swap(x, y);
        comp--;
        siz[x] += siz[y];
        p[y] = x;
        return 1;
    }
};

int get_cycles(vector<int> p) {
    int n = p.size();

    vector<int> used(n);
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        if(used[i]) continue;

        int j = i;
        while(!used[j]) {
            used[j] = 1;
            j = p[j];
        }

        cnt++;
    }

    return cnt;
}

long long solve_zero(vector<array<int, 3>> a) {
    int n = (int) a.size();
    int N = n + 1;
    vector<vector<array<int, 3>>> g(N + 1);
    for(int i = 0; i < n; i++) {
        auto [u, v, w] = a[i];
        g[u].push_back({v, w, i});
        g[v].push_back({u, w, i});
    }
    vector<pair<int, int>> parent(N + 1);
    vector<int> used(N + 1), d(N + 1);

    int extra_edge = -1;
    function<void(int, int)> dfs = [&](int v, int p) {
        used[v] = 1;
        for(auto [to, w, idx] : g[v]) {
            if(to == p) continue;
            if(used[to]) {
                extra_edge = idx;
                continue;
            }

            parent[to] = {v, idx};
            d[to] = d[v] + 1;
            dfs(to, v);
        }
    };
    dfs(N, 0); dfs(1, 0);

    assert(extra_edge != -1);
    parent[1] = {N, extra_edge};

    int sign = 1;
    vector<int> p(n);
    for(int v = 1; v <= n; v++) {
        auto [u, idx] = parent[v];
        p[idx] = v - 1;
        if(v > u) sign *= -1;
    }
    int cnt_cycles = get_cycles(p);
    if((n - cnt_cycles) & 1) sign = -sign;

    long long ans = inf;
    int best_idx = extra_edge;
    if(sign == 1) ans = min(ans, (long long) a[extra_edge][2]);

    int v = a[extra_edge][0];
    int u = a[extra_edge][1];
    if(d[v] < d[u]) swap(u, v);

    int prev = u;
    while(v != u) {
        auto [par, idx] = parent[v];

        // Delete (v, p)
        // Add (v, prev)
        sign *= -1;
        if(v > par) sign *= -1;
        if(v > prev) sign *= -1;
        if(sign == 1) ans = min(ans, (long long) a[idx][2]);

        if(a[idx][2] < a[best_idx][2]) best_idx = idx;

        prev = v;
        v = par;
    }

    long long two_operations = inf;
    for(int i = 0; i < n; i++) {
        if(i != best_idx) two_operations = min(two_operations, (long long) a[i][2]);
    }
    two_operations += a[best_idx][2];
    ans = min(ans, two_operations);

    return ans;
}

long long get(vector<array<int, 3>> a) {
    int n = (int) a.size();

    int N = n + 1;
    for(auto &[l, r, w] : a) r++;

    auto edges = a;
    for(auto &[u, v, w] : edges) {
        swap(u, w);
    }
    sort(edges.rbegin(), edges.rend());

    DSU dsu(N + 1);
    dsu.init();
    long long ans = 0;
    for(auto [w, u, v] : edges) {
        if(!dsu.unite(u, v)) ans += w;
    }

    if(dsu.comp > 1) {
        if(dsu.comp > 2) return ans;
        else {
            int cnt_other = 0, max_other = 0;
            for(int v = 1; v <= N; v++) {
                if(dsu.get(N) != dsu.get(v)) {
                    cnt_other++;
                    max_other = max(max_other, v);
                }
            }

            if(cnt_other < max_other) return ans;
            return solve_zero(a);
        }
    }

    vector<vector<array<int, 3>>> g(N + 1);
    for(int i = 0; i < n; i++) {
        auto [u, v, w] = a[i];
        g[u].push_back({v, w, i});
        g[v].push_back({u, w, i});
    }
    vector<pair<int, int>> parent(N + 1);
    vector<int> sz(N + 1, 1), max_dp(N + 1), weight(N + 1);

    function<void(int, int)> dfs = [&](int v, int p) {
        max_dp[v] = v;

        for(auto [to, w, idx] : g[v]) {
            if(to == p) continue;

            parent[to] = {v, idx};
            weight[to] = w;
            dfs(to, v);
            sz[v] += sz[to];
            max_dp[v] = max(max_dp[v], max_dp[to]);
        }
    };
    dfs(N, 0);

    int sign = 1;
    vector<int> p(n);
    for(int v = 1; v <= n; v++) {
        auto [u, idx] = parent[v];
        p[idx] = v - 1;
        if(v > u) sign *= -1;
    }
    int cnt_cycles = get_cycles(p);
    if((n - cnt_cycles) & 1) sign = -sign;

    ans = inf;
    if(sign == 1) ans = 0;
    else {
        reverse(edges.begin(), edges.end());
        ans = edges[0][0] + edges[1][0];

        for(int v = 1; v < N; v++) {
            if(sz[v] < max_dp[v]) ans = min(ans, (long long) weight[v]);
        }
    }

    return ans;
}

void solve() {
    int n;
    cin >> n;
    vector<array<int, 3>> a(n);
    for(auto &[l, r, w] : a) {
        cin >> l >> r >> w;
    }

    long long ans = get(a);
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider coordinates $$$x$$$ and $$$y$$$ separately. Since $$$1 \le x_i, y_i \le m - 1$$$, after each step both coordinates increase and remain connected with the previous square.

From the picture we can see that each coordinate spans from the bottom-left corner of the first square to the top-right corner of the last square.

To calculate the perimeter we can add the length of that interval for both coordinates and multiply it by $$$2$$$, as it is counted in the perimeter twice, going in both directions:

The coordinates of the bottom-left corner of the first square are $$$(x_1, y_1)$$$ and of the top-right corner of the last square are $$$(m + \sum\limits_{i = 1}^n x_i, m + \sum\limits_{i = 1}^n y_i)$$$.

The lengths of the intervals are $$$m + \sum\limits_{i = 2}^n x_i$$$ and $$$m + \sum\limits_{i = 2}^n y_i$$$.

Therefore, the answer is $$$2(2m + \sum\limits_{i = 2}^n (x_i + y_i))$$$.

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> x(n), y(n);
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    int ans = 2 * (accumulate(x.begin(), x.end(), 0) + m - x[0] + accumulate(y.begin(), y.end(), 0) + m - y[0]);
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

Consider two elements $$$x \lt y$$$. Suppose their positions in $$$p$$$ are $$$i$$$ and $$$j$$$ correspondigly.

How can we determine if $$$i \lt j$$$? If $$$i \lt j$$$ and $$$x \lt y$$$, we will have $$$g_{x, y} = g_{y, x} = 1$$$. Otherwise, $$$i \gt j$$$ and $$$x \lt y$$$, so $$$g_{x, y} = g_{y, x} = 0$$$.

So if $$$g_{x, y} = 1$$$, we know that $$$i \lt j$$$, otherwise $$$i \gt j$$$.

That way we can determine for each pair of elements which one of them should appear earlier in the permutation. Notice that this is just a definition of a comparator, which proves that the permutation is indeed unique. We can find it by sorting $$$p = [1, 2, \ldots, n]$$$ with that comparator.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<string> g(n);
    for(auto &i : g) {
        cin >> i;
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(),
    [&](int x, int y) {
        if(g[x][y] == '1') return x < y;
        else return x > y;
    });
    for(auto i : p) cout << i + 1 << " "; cout << '\n';
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

If $$$[a_1, a_2, \ldots, a_k, a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n]$$$ is a palindrome, then $$$[a_1, a_2, \ldots, a_k, a_i, a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n]$$$ is also a palindrome for all $$$k \lt i \lt n - k + 1$$$, because we make it's length odd and add $$$a_i$$$ to the middle.

We can use this to create a sequence with a big value of $$$g$$$. However, we shouldn't create a palindrome of a greater length than $$$2k + 1$$$ by using the fact above.

That make us try something like $$$a = [1, 2, 3, \ldots, n - 2, 1, 2]$$$. $$$f(a) = 3$$$ here, and any of $$$[a_1, a_i, a_{n - 1}]$$$ for $$$1 \lt i \lt n - 1$$$ and $$$[a_2, a_i, a_n]$$$ for $$$2 \lt i \lt n$$$ are palindromes, which means that $$$g(a) = 2(n - 3) = 2n - 6$$$.

This construction works for $$$n \ge 7$$$, so we have to handle $$$n = 6$$$ separately.

We can also use the construction from the example with $$$n = 6$$$ directly: $$$a = [1, 1, 2, 3, 4, \ldots, n - 3, 1, 2]$$$, which has $$$g(a) = 3n - 11$$$.

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    if (n == 6) {
        cout << "1 1 2 3 1 2\n";
    }
    else if(n == 9) {
        cout << "7 3 3 7 5 3 7 7 3\n";
    }
    else if(n == 15) {
        cout << "15 8 8 8 15 5 8 1 15 5 8 15 15 15 8\n";
    }
    else {
        for(int i = 1; i <= n - 2; i++) cout << i << " "; cout << "1 2\n";
    }
}


signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

When is a subarray $$$a[l, r]$$$ not good?

If $$$r - l + 1$$$ is odd, $$$a[l, r]$$$ can't be bad. Otherwise, suppose the median of $$$a[l, r]$$$ is $$$x$$$. Then there need to be exactly $$$\frac{r - l + 1}{2}$$$ elements in $$$a[l, r]$$$ that are $$$\le x$$$ and exactly $$$\frac{r - l + 1}{2}$$$ that are $$$ \gt x$$$.

This gives us an idea to calculate the number of bad subarrays with a median of $$$x$$$.

Create another array $$$b$$$ of size $$$n$$$, where $$$b_i = -1$$$ if $$$a_i \le x$$$ and $$$b_i = 1$$$ otherwise.

$$$a[l, r]$$$, which has a median of $$$x$$$, is bad if and only if $$$\sum\limits_{i = l}^r b_i = 0$$$ and $$$r - l + 1$$$ is even.

Notice that the second condition is not needed, as the sum of an odd length subarray of $$$b$$$ is always odd, so it can't be zero.

Therefore, $$$a[l, r]$$$ with a median of $$$x$$$ is bad iff $$$\sum\limits_{i = l}^r b_i = 0$$$.

If there is no $$$x$$$ in $$$[l, r]$$$, then the median of $$$a[l, r]$$$ trivially can't be equal to $$$x$$$.

If there is an occurrence of $$$x$$$ in $$$a[l, r]$$$ and $$$\sum\limits_{i = l}^r b_i = 0$$$, notice that the median of $$$a[l, r]$$$ will always be exactly $$$x$$$. This is true because $$$\frac{r - l + 1}{2}$$$ smallest elements of $$$a[l, r]$$$ are all $$$\le x$$$, and there is an occurrence of $$$x$$$, so $$$\frac{r - l + 1}{2}$$$-th smallest element must be $$$x$$$.

This allows us to simply count the number of subarrays of $$$b$$$ with a sum of $$$0$$$ and with an occurrence of $$$x$$$ to count the number of bad subarrays with median $$$x$$$.

We can subtract that value from $$$\frac{n(n + 1)}{2}$$$ for all $$$x$$$ between $$$1$$$ and $$$A = 10$$$ to solve the problem in $$$O(nA)$$$.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 11;

int main() {
    int tests;
    cin >> tests;
    for(int test = 0; test < tests; test++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto &i : a) {
            cin >> i;
        }
        long long ans = 0;
        for(int x = 1; x < MAX; x++) {
            vector<int> b(n);
            for(int i = 0; i < n; i++) {
                b[i] = (a[i] > x? 1 : -1);
            }
            int sum = n;
            vector<int> pref(n);
            for(int i = 0; i < n; i++) {
                pref[i] = sum;
                sum += b[i];
            }
            vector<int> cnt(2 * n + 1);
            sum = n;
            int j = 0;
            for(int i = 0; i < n; i++) {
                if(a[i] == x) {
                    while(j <= i) {
                        cnt[pref[j]]++;
                        j++;
                    }
                }
                sum += b[i];
                ans += cnt[sum];
            }
        }
        ans = 1ll * n * (n + 1) / 2 - ans;
        cout << ans << '\n';
    }
    return 0;
}

Any good set has a tree-like structure.

Specifically, represent $$$S$$$ as a forest the following way: segment $$$[l, r]$$$ has a parent $$$[L, R]$$$ iff $$$[l, r] \in [L, R]$$$ and $$$R - L + 1$$$ is minimized (its parent is the shortest interval in which it lies). This segment is unique (or does not exist), because there can't be two segments with minimum length that cover $$$[l, r]$$$, as they would partially intersect otherwise.

Notice that we can always add $$$[1, n]$$$ and $$$[i, i]$$$ for all $$$1 \le i \le n$$$ if they aren't in $$$S$$$ yet. Now the forest of $$$S$$$ is a tree with exactly $$$n$$$ leaves.

Suppose $$$[L, R]$$$ has $$$k$$$ children $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$. If $$$k \gt 2$$$, we can always add $$$[l_1, r_2]$$$ to $$$S$$$, which decreases the number of children of $$$[L, R]$$$ by $$$1$$$ and increases the size of $$$S$$$ by $$$1$$$.

Therefore, in the optimal solution each segment has at most $$$2$$$ children. Having exactly one child is impossible, as we have added all $$$[i, i]$$$, so every index of $$$[L, R]$$$ is covered by its children.

This means that we have a tree where each vertex has either $$$0$$$ or $$$2$$$ children, which is a full binary tree.

We have $$$n$$$ leaves, and every full binary tree with $$$n$$$ leaves has exactly $$$2n - 1$$$ vertices, so this is always the optimal size of $$$T$$$ regardless of $$$S$$$.

To count the number of $$$T$$$, notice that when $$$m = 0$$$ the answer is the number of full binary trees with $$$n$$$ leaves, which is $$$C_{n - 1}$$$, where $$$C$$$ denotes the Catalan's sequence.

To extend this to a general tree, we can add $$$[1, n]$$$ and $$$[i, i]$$$ for all $$$1 \le i \le n$$$ to $$$S$$$.

Now suppose $$$[L, R]$$$ has $$$k \ge 2$$$ children $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$. We need to merge some children. We can treat $$$[l_1, r_1]$$$ as $$$[1, 1]$$$, $$$[l_2, r_2]$$$ as $$$[2, 2]$$$, etc. This is now the same case as $$$m = 0$$$, so there are $$$C_{k - 1}$$$ ways to merge children of $$$[L, R]$$$.

Each vertex is independent of each other, so the answer is $$$\prod C_{c_v - 1}$$$ over all non-leaves $$$v$$$, where $$$c_v$$$ is the number of children of $$$v$$$.

We can construct the tree in $$$O(n \log n)$$$ by definition or in $$$O(n)$$$ using a stack.

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;
const int MAX = 4e5 + 42;

int fact[MAX], inv[MAX], inv_fact[MAX];

int C(int n, int k) {
    if(n < k || k < 0) return 0;
    return (long long) fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod;
}

int Cat(int n) {
    return (long long) C(2 * n, n) * inv[n + 1] % mod;
}

int binpow(int x, int n) {
    int ans = 1;
    while(n) {
        if(n & 1) ans = (long long) ans * x % mod;
        n >>= 1;
        x = (long long) x * x % mod;
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    int initial_m = m;
    vector<pair<int, int>> a(m);
    for(auto &[l, r] : a) {
        cin >> l >> r;
    }
    bool was_full = 0;
    vector<int> was_single(n + 1);
    for(auto [l, r] : a) was_full |= (r - l + 1 == n);
    for(auto [l, r] : a) {
        if(l == r) was_single[l] = 1;
    }
    if(!was_full) {
        a.push_back({1, n});
        m++;
    }
    for(int i = 1; i <= n; i++) {
        if(!was_single[i] && n != 1) {
            a.push_back({i, i});
            m++;
        }
    }
    for(auto &[l, r] : a) r = -r;
    sort(a.begin(), a.end());
    vector<int> deg(m);
    for(int i = 0; i < m; i++) {
        int j = i + 1;
        while(j < m) {
            if(-a[i].second < a[j].first) break;
            deg[i]++;
            j = upper_bound(a.begin(), a.end(), make_pair(-a[j].second, 1)) - a.begin();
        }
    }
    for(auto &[l, r] : a) r = -r;
    int ans = 1;
    for(int i = 0; i < m; i++) {
        if(deg[i] > 0) {
            assert(deg[i] >= 2);
            ans = (long long) ans * Cat(deg[i] - 1) % mod;
        }
    }
    cout << ans << '\n';
}

signed main() {
    fact[0] = 1;
    for(int i = 1; i < MAX; i++) fact[i] = (long long) fact[i - 1] * i % mod;
    inv_fact[MAX - 1] = binpow(fact[MAX - 1], mod - 2);
    for(int i = MAX - 1; i; i--) inv_fact[i - 1] = (long long) inv_fact[i] * i % mod;
    assert(inv_fact[0] == 1);
    for(int i = 1; i < MAX; i++) inv[i] = (long long) inv_fact[i] * fact[i - 1] % mod;
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

The order of the sequence doesn't matter, so let's fix the sequence $$$\text{cnt}$$$ and calculate its contribution to the answer.

For a fixed $$$\text{cnt}$$$, the number of ways to order $$$a$$$ is $$$\binom{n}{\text{cnt}_0, \text{cnt}_1, \ldots, \text{cnt}_{m - 1}}$$$. By Lucas's theorem the contribution is odd iff for each set bit in $$$n$$$ there is exactly one $$$i$$$ such that $$$\text{cnt}_i$$$ has this bit set, and $$$\sum\limits_{i = 0}^{m - 1} \text{cnt}_i = n$$$. In other words, $$$\text{cnt}$$$ has to partition all set bits in $$$n$$$.

Since $$$\text{cnt}$$$ partitions the bits of $$$n$$$, there will be $$$i$$$ which has it's most significant bit. This means that $$$2\text{cnt}_i \gt n$$$, so $$$i$$$ will always be the median.

Suppose there are $$$p$$$ non-zero elements in $$$\text{cnt}$$$. We can partition all set bits of $$$n$$$ into $$$p$$$ non-empty subsequences and then choose which of the $$$m$$$ numbers will occur.

The only time we use the value of $$$n$$$ is when we partition all of it's set bits into subsequences. That means that the answer only depends on the number of set bits in $$$n$$$, not on $$$n$$$ itself.

So let's fix $$$p$$$ as the number of non-zero elements in $$$\text{cnt}$$$ and $$$x$$$ as the median. Denote $$$b$$$ as the number of set bits in $$$n$$$. There are $$$S(b, p)$$$ ways to partition the bits into $$$p$$$ non-empty subsequences, where $$$S$$$ denotes Stirling number of the second kind. There are $$$\binom{x}{p - 1}$$$ ways to choose which other elements will have non-zero $$$\text{cnt}$$$, because the median will always have the largest value and non-zero $$$\text{cnt}_i$$$ must be non-decreasing.

The answer is then $$$\oplus_{p = 1}^b \oplus_{x = 0}^{m - 1} \left(S(b, p) \bmod 2\right) \cdot \left(\binom{x}{p - 1} \bmod 2\right) \cdot x$$$, which we can calculate in $$$O(km)$$$, which solves the easy version.

To solve the hard version we can use Lucas's theorem again to get that the contribution of $$$x$$$ to the answer is the XOR of $$$S(b, p + 1) \bmod 2$$$ over all submasks $$$p$$$ of $$$x$$$. We can limit $$$p$$$ to be between $$$0$$$ and $$$b - 1$$$.

That means that only $$$L = \lceil \log_2 b \rceil$$$ last bits of $$$x$$$ determine whether $$$x$$$ contributes something to the answer. We can find which of $$$2^L$$$ of them will have an odd contribution by setting $$$dp_p = S(b, p + 1) \bmod 2$$$, and calculating it's SOS-dp. Then for fixed $$$L$$$ last bits it is easy to find the XOR of all $$$x \lt m$$$ with those bits.

Note that $$$S(n, k)$$$ is odd iff $$$(n - k) \text{&} \frac{k - 1}{2} = 0$$$, which we can derive from the recurrence, combinatorics, google or OEIS.

This solves the problem in $$$O(b \log b) = O(k \log k)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int C(int n, int k) {
    return (n & k) == k;
}
 
int S(int n, int k) {
    return !(n - k & (k - 1 >> 1));
}
 
int brute_partition(int n, int m) {
    vector<int> cnt;
    int ans = 0;
    for(int k = 1; k <= n; k++) {
        if(!S(n, k)) continue;
        for(int median = 1; median < m; median++) {
            if(C(median, k - 1)) ans ^= median;
        }
    }
    return ans;
}
 
void solve() {
    int k, m;
    string s;
    cin >> k >> m >> s;
    int n = 0;
    for(auto &i : s) n += i & 1;
    int ans = brute_partition(n, m);
    cout << ans << '\n';
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

int S(int n, int k) {
    return !(n - k & (k - 1 >> 1));
}

int get(int n, int m) {
    int L = __lg(n) + 1;
    int up = 1 << L;
    vector<int> dp(up);
    for(int i = 0; i < n; i++) dp[i] = S(n, i + 1);
    for(int j = 0; j < L; j++) {
        for(int i = 0; i < up; i++) {
            if(i >> j & 1) dp[i] ^= dp[i ^ (1 << j)];
        }
    }
    int ans = 0;
    for(int lst = 0; lst < up && lst < m; lst++) {
        if(!dp[lst]) continue;
        int cnt = m - 1 - lst >> L;
        if(cnt & 1 ^ 1) ans ^= lst;
        if(cnt % 4 == 0) ans ^= cnt << L;
        else if(cnt % 4 == 1) ans ^= 1ll << L;
        else if(cnt % 4 == 2) ans ^= cnt + 1 << L;
        else ans ^= 0;
    }
    return ans;
}

void solve() {
    int k, m;
    string s;
    cin >> k >> m >> s;
    int n = 0;
    for(auto &i : s) n += i & 1;
    int ans = get(n, m);
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

import requests
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.cluster import KMeans
from collections import defaultdict

# Function to fetch all users from Codeforces API
def fetch_users():
    url = "https://mirror.codeforces.com/api/user.ratedList"
    response = requests.get(url)

    if response.status_code == 200:
        data = response.json()
        if data["status"] == "OK":
            return data["result"]
        else:
            print("Error in response: ", data["comment"])
    else:
        print("Error fetching data: ", response.status_code)
    return []

# Function to filter users by max rating
def filter_users_by_rating(users, min_rating):
    return [user for user in users if user.get('maxRating', 0) > min_rating]

# Function to cluster users by the similarity of their names
def cluster_users_by_name(usernames, num_clusters=10):
    # Vectorize the usernames using TF-IDF with character n-grams
    vectorizer = TfidfVectorizer(analyzer='char', ngram_range=(2, 3))
    X = vectorizer.fit_transform(usernames)

    # Perform k-means clustering
    kmeans = KMeans(n_clusters=num_clusters, random_state=42)
    clusters = kmeans.fit_predict(X)

    clustered_users = defaultdict(list)
    user_cluster_map = {}
    for username, cluster_id in zip(usernames, clusters):
        clustered_users[cluster_id].append(username)
        user_cluster_map[username] = cluster_id

    return clustered_users, user_cluster_map

# Main processing function
def process_users(min_rating, num_clusters):
    # Fetch users
    users = fetch_users()

    # Filter users by max rating
    filtered_users = filter_users_by_rating(users, min_rating)
    print(len(filtered_users))
    # Extract usernames
    usernames = [user["handle"] for user in filtered_users]

    # Cluster users by the similarity of their names
    clusters, user_cluster_map = cluster_users_by_name(usernames, num_clusters)

    return clusters, user_cluster_map

# Fetch and process users (run this once)
clusters, user_cluster_map = process_users(min_rating=1599, num_clusters=5000)

from google.colab import files

def save_clusters_to_file(clusters, filename="clusters.txt"):
    with open(filename, "w") as file:
        for cluster_id, user_list in clusters.items():
            cluster_size = len(user_list)
            file.write(f"{cluster_size} {' '.join(user_list)}\n")
    return filename

output_file = save_clusters_to_file(clusters)

# Provide a link to download the file in Google Colab
files.download(output_file)

def get_user_cluster(username):
    cluster_id = user_cluster_map.get(username, None)
    if cluster_id is not None:
        return clusters[cluster_id]
    else:
        return "User not found"

# Example usage
username = "nifeshe"
user_cluster = get_user_cluster(username)
if user_cluster != "User not found":
    print(len(user_cluster))
    print(f"The cluster for user '{username}' is: {user_cluster}")
else:
    print(user_cluster)