Both versions have the same underlying idea: we want to maximize the product of two sums.

The optimal construction places one point at $$$(x, 0)$$$, another at $$$(0, y)$$$, and the third at the origin. The doubled area of the resulting triangle is

In the easy version, every move has length $$$1$$$. Therefore, if we split the $$$n$$$ operations into two groups, the sums of the groups are simply their sizes. Let the sizes be $$$x$$$ and $$$n-x$$$. We need to maximize

This product is maximized when the two groups are as balanced as possible. Hence, we take

The answer is therefore

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        cout << (n / 2) * ((n + 1) / 2) << '\n';
    }

    return 0;
}

Time complexity: $$$O(1)$$$ per test case.

Space complexity: $$$O(1)$$$.

As in the easy version, we want to maximize the product of the sums of the two groups.

Let the length of move $$$i$$$ be $$$w_i = 2^{a_i}$$$, and let

be the sum of all move lengths. If one group has sum $$$x$$$, the other group has sum $$$S-x$$$, so our goal is to maximize

This expression is maximized when $$$x$$$ is as close as possible to $$$S/2$$$. Since every subset has a complementary subset, it is enough to find the largest achievable subset sum not exceeding $$$\lfloor S/2\rfloor$$$.

We can find this sum greedily. Sort the move lengths in decreasing order and process them one by one. Add the current move to the chosen group if doing so does not make its sum exceed $$$\lfloor S/2\rfloor$$$.

The important property is that every move length is a power of two. This makes the greedy choice optimal. Consider a move length $$$2^k$$$, after all larger moves have been considered, and let $$$r$$$ be the remaining capacity. The greedy algorithm takes $$$q = \min(c, \lfloor r/2^k \rfloor)$$$ moves of this length, where $$$c$$$ is the number of available moves of length $$$2^k$$$. Suppose another feasible selection takes only $$$j \lt q$$$ such moves. If its selected smaller moves have total length less than $$$(q-j)2^k$$$, then its total at this and all smaller powers is less than $$$q2^k$$$, so it cannot be better than the greedy choice. Otherwise, those smaller moves have total length at least $$$(q-j)2^k$$$. By repeatedly pairing two equal powers and replacing them with the next power of two, we can extract a subcollection whose sum is exactly $$$(q-j)2^k$$$. Replacing that subcollection with the missing $$$q-j$$$ moves of length $$$2^k$$$ preserves the total sum. Therefore, there is an optimal selection that agrees with the greedy choice at this power. Applying this argument from the largest power to the smallest proves that the greedy construction obtains the largest subset sum not exceeding the target.

After finding this sum $$$x$$$, the answer is

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        vector<ll> a(n);
        ll sum = 0;
        for (auto &x : a) {
            int v;
            cin >> v;
            x = 1LL << v;
            sum += x;
        }

        sort(a.rbegin(), a.rend());

        ll x = 0;
        for (ll v : a) {
            if (x + v <= sum / 2) {
                x += v;
            }
        }

        cout << x * (sum - x) << '\n';
    }

    return 0;
}

Time complexity: $$$O(n\log n)$$$ per test case, due to sorting.

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

Approach: Sort + Construct

First, notice that every occurrence of the maximum element is always very pleasant, because no previous element can be larger than it.

Therefore, if the maximum occurs more than $$$k$$$ times, the answer is NO.

Otherwise:

1. Sort the array in ascending order.
2. Print the largest $$$k$$$ elements in ascending order.
3. Print the remaining $$$n-k$$$ elements in descending order.

Why does this work?

• The first $$$k$$$ elements are sorted, so every one is very pleasant.
• Since the maximum occurs at most $$$k$$$ times, the average of these first $$$k$$$ elements is strictly greater than every remaining element.
• The remaining elements are printed in descending order. Each is smaller than the current average, and adding such an element decreases the average while keeping it greater than the current element. Thus, every remaining element is NOT very pleasant.

Exactly $$$k$$$ very pleasant donations!

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, k;
        cin >> n >> k;

        vector<long long> a(n);
        for (auto &x : a) cin >> x;

        sort(a.begin(), a.end());

        int cnt = count(a.begin(), a.end(), a.back());

        if (cnt > k) {
            cout << "NO\n";
            continue;
        }

        cout << "YES\n";

        for (int i = n - k; i < n; i++) {
            cout << a[i] << ' ';
        }

        for (int i = n - k - 1; i >= 0; i--) {
            cout << a[i] << ' ';
        }

        cout << '\n';
    }

    return 0;
}

Complexity: $$$O(N \log N)$$$ time and $$$O(N)$$$ space per test case.

Approach: Make Every Element Prime

Basically, the easiest way to guarantee that an array is not disgusting is to make every element prime.

Why does this work?

For any two primes:

• If they are different, their GCD is $$$1$$$.
• If they are equal, their GCD equals the smaller element.

So neither case can be disgusting.

1. Find the next prime

For every $$$a[i]$$$:

• If it is already prime, leave it unchanged.
• Otherwise, replace it with the smallest prime greater than it.

Let that prime be $$$p$$$. Perform one operation with:

This operation is valid because:

2. Check the restrictions

By Bertrand's postulate, for every integer $$$a[i] \gt 1$$$, there is a prime strictly between $$$a[i]$$$ and $$$2a[i]$$$.

Therefore:

• $$$x \le a[i]$$$, so the total sum of increments is at most the original array sum.
• At most one operation is performed per element, giving at most $$$n$$$ operations.

Both restrictions are satisfied.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    const int M = 200000;
    vector<bool> prime(M + 1, true);

    prime[0] = prime[1] = false;

    for (int i = 2; i * i <= M; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= M; j += i) {
                prime[j] = false;
            }
        }
    }

    vector<int> nxt(100001);
    int p = -1;

    for (int i = M; i >= 2; i--) {
        if (prime[i]) p = i;
        if (i <= 100000) nxt[i] = p;
    }

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int &x : a) {
            cin >> x;
            x = nxt[x];
        }

        for (int x : a) cout << x << ' ';
        cout << '\n';
    }

    return 0;
}

Complexity: $$$O(M \log\log M + N)$$$ preprocessing and processing, where $$$M = 200000$$$. Extra space: $$$O(M)$$$.

Approach: GCD + BFS on a Small Interval

Unlike C1, here we are given a fixed starting value $$$a$$$ and target $$$b$$$. We must find the minimum number of operations, not just any valid construction.

Basically, an operation changes the current value $$$u$$$ to $$$v = u + x$$$.

The condition $$$\gcd(u,x)=1$$$ is equivalent to:

So we can view the problem as finding the shortest increasing path from $$$a$$$ to $$$b$$$, where an edge from $$$u$$$ to $$$v$$$ exists whenever their GCD is $$$1$$$.

1. Handle 0 and 1 operations

• If $$$a=b$$$, the answer is $$$0$$$.
• If $$$\gcd(a,b)=1$$$, the answer is $$$1$$$, with increment $$$b-a$$$.

2. Check whether 2 operations are possible

We need an intermediate integer $$$c$$$ such that:

Equivalently:

We only need to search the first $$$4096$$$ integers after $$$a$$$.

Why $$$4096$$$? Since $$$a\cdot b \le 10^{14}$$$, it has at most $$$12$$$ distinct prime factors. By Kanold's bound on the Jacobsthal function, every block of $$$2^{12}=4096$$$ consecutive integers contains an integer coprime to $$$a\cdot b$$$.

Therefore, if no intermediate is found, we know that $$$b-a \le 4096$$$.

3. Use BFS for the remaining cases

Now the interval $$$[a,b]$$$ contains at most $$$4097$$$ vertices.

Create an edge $$$u \to v$$$ whenever $$$u \lt v$$$ and $$$\gcd(u,v)=1$$$.

Run ordinary BFS from $$$a$$$ to $$$b$$$, store parents, and reconstruct the shortest path.

The increments are simply the differences between consecutive vertices.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        long long a, b;
        cin >> a >> b;

        if (a == b) {
            cout << 0 << "\n";
            continue;
        }

        if (gcd(a, b) == 1) {
            cout << 1 << "\n" << b - a << '\n';
            continue;
        }

        long long c = -1, ab = a * b;

        for (long long x = a + 1; x < b && x <= a + 4096; x++) {
            if (gcd(ab, x) == 1) {
                c = x;
                break;
            }
        }

        if (c != -1) {
            cout << 2 << "\n" << c - a << ' ' << b - c << '\n';
            continue;
        }

        int d = b - a;
        assert(d <= 4096);

        vector<int> par(d + 1, -1), q = {0};
        par[0] = 0;

        for (int h = 0; h < (int)q.size() && par[d] == -1; h++) {
            int u = q[h];

            for (int v = u + 1; v <= d; v++) {
                if (par[v] == -1 && gcd(a + u, a + v) == 1) {
                    par[v] = u;
                    q.push_back(v);

                    if (v == d) break;
                }
            }
        }

        vector<int> ans;

        for (int v = d; v; v = par[v]) {
            ans.push_back(v - par[v]);
        }

        reverse(ans.begin(), ans.end());

        cout << ans.size() << '\n';
        for (int x : ans) cout << x << ' ';
        cout << '\n';
    }

    return 0;
}

Complexity: The direct checks take $$$O(4096\log B)$$$. In the exceptional case, BFS has at most $$$4097$$$ vertices and takes $$$O(D^2\log B)$$$, where $$$D=b-a\le4096$$$.

The important distinction in C2 is that BFS is necessary to guarantee the minimum number of operations. Finding any valid intermediate is enough only when the answer is exactly $$$2$$$.

Approach: Bipartite Coloring

The important observation is that bipartiteness never changes after PUB performs an operation.

The chosen path has $$$2k-1$$$ edges, so its endpoints are at odd distance.

• If the graph is bipartite, adding an edge between those endpoints preserves bipartiteness. Removing an edge also preserves it.
• Conversely, after the operation, the removed edge has an alternative path of length $$$2k-1$$$ through the added edge. Thus, if the resulting graph is bipartite, restoring the removed edge also preserves it.

Therefore, bipartiteness is invariant.

First run

If $$$s$$$ contains only zeros, construct a triangle and connect all remaining vertices to vertex $$$1$$$. This gives a non-bipartite graph.

Otherwise, choose any vertex $$$x$$$ corresponding to a $$$1$$$.

• Connect vertex $$$1$$$ to every vertex corresponding to a $$$1$$$.
• Connect vertex $$$x$$$ to every vertex corresponding to a $$$0$$$.

This produces a connected bipartite tree.

Second run

• If the graph is not bipartite, output all zeros.
• Otherwise, BFS-color the graph. The original bit is the XOR of the color of vertex $$$1$$$ and the color of the corresponding vertex.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string op;
    cin >> op;

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        if (op == "first") {
            string s;
            cin >> s;

            int x = -1;
            for (int i = 0; i < n - 1; i++) {
                if (s[i] == '1') x = i + 2;
            }

            vector<pair<int, int>> e;

            if (x == -1) {
                e = {{1, 2}, {2, 3}, {3, 1}};
                for (int i = 4; i <= n; i++) {
                    e.push_back({1, i});
                }
            } else {
                for (int i = 2; i <= n; i++) {
                    if (s[i - 2] == '1') e.push_back({1, i});
                    else e.push_back({x, i});
                }
            }

            cout << e.size() << '\n';
            for (auto [u, v] : e) {
                cout << u << ' ' << v << '\n';
            }
        } else {
            int m;
            cin >> m;

            vector<vector<int>> g(n);

            while (m--) {
                int u, v;
                cin >> u >> v;
                --u;
                --v;

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

            vector<int> c(n, -1);
            queue<int> q;

            c[0] = 0;
            q.push(0);

            bool ok = true;

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (int v : g[u]) {
                    if (c[v] == -1) {
                        c[v] = c[u] ^ 1;
                        q.push(v);
                    } else if (c[v] == c[u]) {
                        ok = false;
                    }
                }
            }

            string s(n - 1, '0');

            if (ok) {
                for (int i = 1; i < n; i++) {
                    s[i - 1] = '0' + (c[0] ^ c[i]);
                }
            }

            cout << s << '\n';
        }
    }

    return 0;
}

Complexity: $$$O(N)$$$ for the first run and $$$O(N+M)$$$ for the second run.

Approach: BFS Prefixes + Binary Search

The trick is to use BFS-order prefixes as connected subsets. That turns the bipartiteness query into a monotonic binary-search oracle. We can find one secret edge in at most $$$33$$$ queries.

1. The two hidden edges connect the same components

Fix a bipartite coloring of every connected component of the original graph.

Adding an edge between two different components imposes a constraint on how their colorings must be flipped. Since adding either secret edge individually preserves bipartiteness, but adding both does not, the two edges must connect the same pair of distinct components, say $$$A$$$ and $$$B$$$, with contradictory coloring constraints.

Consequently, both secret edges have:

• One endpoint in $$$A$$$.
• One endpoint in $$$B$$$.

2. Turn query 1 into a binary-search predicate

Build a BFS spanning tree for every connected component and concatenate their BFS orders into one array order.

An important property: every prefix of a BFS order is connected in its spanning tree. Every included vertex has its BFS parent included as well.

Therefore, if we select a prefix of order, the two selected endpoints within any original component are guaranteed to be connected whenever both are present.

Since both secret edges are needed to create an odd cycle, the queried induced graph is non-bipartite exactly when all four secret endpoints are included.

Now binary-search the smallest prefix length $$$p$$$ for which the answer is non-bipartite.

The vertex order[p-1] is necessarily one of the four secret endpoints. Let its component be $$$A$$$.

3. Find an endpoint in the other component

Keep all vertices of $$$A$$$ selected.

Remove $$$A$$$ from order, and binary-search the prefix of the remaining vertices until the induced graph becomes non-bipartite.

The last vertex added is an endpoint of the hidden edges in the other component $$$B$$$.

Call the two discovered endpoints $$$u$$$ and $$$v$$$.

4. Recover the edge

Ask whether $$$(u,v)$$$ is a secret edge using query type 2.

• If yes, output it.
• Otherwise, both endpoint pairs are distinct, and the two secret edges form the crossed matching.

Now choose the smaller of components $$$A$$$ and $$$B$$$. Its discovered endpoint is already known.

Re-root its BFS spanning tree at that endpoint. Every prefix of this new BFS order is connected and contains the root.

Keep the other component completely selected and binary-search the prefix that first makes the graph non-bipartite. The newly added vertex is the other endpoint in the smaller component.

Pair it with the previously discovered endpoint from the larger component. This is guaranteed to be one of the secret edges.

5. Query count

The smaller component has at most $$$n/2 \le 1000$$$ vertices, which is why the final search needs at most $$$10$$$ queries.

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

namespace local {

using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;

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

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

struct DSU {
    vi p, sz;
    DSU(int n = 0) { init(n); }

    void init(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }

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

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

struct Graph {
    int n;
    vvi adj, tree, parts;
    vi comp, order;

    Graph(int n = 0) : n(n), adj(n), tree(n), comp(n, -1) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void build() {
        for (int s = 0; s < n; s++) {
            if (comp[s] != -1) continue;

            int id = parts.size();
            parts.emplace_back();

            queue<int> q;
            q.push(s);
            comp[s] = id;

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                order.push_back(u);
                parts[id].push_back(u);

                for (int v : adj[u]) {
                    if (comp[v] == -1) {
                        comp[v] = id;
                        tree[u].push_back(v);
                        tree[v].push_back(u);
                        q.push(v);
                    }
                }
            }
        }
    }

    // Any prefix of this order is connected to root.
    vi rooted_order(int root, int id) const {
        vi par(n, -1), res;
        queue<int> q;

        q.push(root);
        par[root] = root;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            res.push_back(u);

            for (int v : tree[u]) {
                if (comp[v] == id && par[v] == -1) {
                    par[v] = u;
                    q.push(v);
                }
            }
        }

        return res;
    }
};

struct Oracle {
    int used = 0;

    int ask1(const vi& s) {
        if (++used > 33 || s.empty()) exit(0);

        cout << "? 1 " << s.size();
        for (int v : s) cout << ' ' << v + 1;
        cout << endl;

        int r;
        if (!(cin >> r) || r == -1) exit(0);
        return r;
    }

    int ask2(int u, int v) {
        if (++used > 33) exit(0);

        cout << "? 2 " << u + 1 << ' ' << v + 1 << endl;

        int r;
        if (!(cin >> r) || r == -1) exit(0);
        return r;
    }

    void answer(int u, int v) {
        cout << "! " << u + 1 << ' ' << v + 1 << endl;
    }
};

// lo is known false, hi is known true.
template<class F>
int first_bad(int lo, int hi, F make, Oracle& io) {
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;

        if (io.ask1(make(mid)) == 0) hi = mid;
        else lo = mid;
    }

    return hi;
}

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, m;
        cin >> n >> m;

        local::Graph G(n);

        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            --u;
            --v;
            G.add_edge(u, v);
        }

        G.build();

        local::Oracle io;

        // Find the last secret endpoint in the whole forest order.
        int p = local::first_bad(0, n, [&](int x) {
            return local::vi(G.order.begin(), G.order.begin() + x);
        }, io);

        int u = G.order[p - 1];
        int cu = G.comp[u];

        // Keep cu completely and binary-search the other component.
        local::vi rest;
        for (int v : G.order) {
            if (G.comp[v] != cu) rest.push_back(v);
        }

        int q = local::first_bad(0, rest.size(), [&](int x) {
            local::vi s = G.parts[cu];
            s.insert(s.end(), rest.begin(), rest.begin() + x);
            return s;
        }, io);

        int v = rest[q - 1];
        int cv = G.comp[v];

        if (io.ask2(u, v)) {
            io.answer(u, v);
            continue;
        }

        int small = (G.parts[cu].size() <= G.parts[cv].size() ? cu : cv);
        int large = (small == cu ? cv : cu);
        int root = (small == cu ? u : v);
        int other = (small == cu ? v : u);

        local::vi ord = G.rooted_order(root, small);
        assert(ord.size() >= 2);

        // The root is already included, so find the other endpoint.
        int pos = local::first_bad(1, ord.size(), [&](int x) {
            local::vi s = G.parts[large];
            s.insert(s.end(), ord.begin(), ord.begin() + x);
            return s;
        }, io);

        int w = ord[pos - 1];
        io.answer(w, other);
    }

    return 0;
}

Complexity: $$$O(n+m)$$$ local preprocessing per test case. At most $$$33$$$ queries, each transmitting at most $$$n$$$ vertices. Extra space: $$$O(n+m)$$$.

The important detail is that the final search is performed in the smaller component. That is what makes the exact $$$33$$$-query bound work.

The key is to track which original elements currently map to each value, rather than simulating the transformation separately for every possible superset.

All original elements that currently have the same value are placed in one group. A transformation only changes the order of these groups and merges two of them. We can therefore maintain the sequence of groups with an implicit treap.

At the same time, we maintain the contribution of the current state using a prefix-product aggregate.

1. Track the groups

Initially, every value belongs to its own group:

G = [{0}, {1}, {2}, ..., {n-1}]

A group contains all original elements that currently map to the same value.

Suppose we are about to apply the transformation

Before this operation, the current groups are

Consider where each group goes:

• The old group $$$G[m-1]$$$ maps to value $$$0$$$.
• The old groups $$$G[0]$$$ and $$$G[m]$$$ both map to value $$$1$$$.
• For every $$$1\le i\le m-2$$$, the old group $$$G[i]$$$ maps to value $$$i+1$$$.

Therefore, the new ordered sequence is

The important detail is that only the first and last groups merge. The penultimate group $$$G[m-1]$$$ remains separate.

When $$$m=1$$$, the two existing groups both map to value $$$0$$$, so they simply merge into one group.

Thus, each operation requires only a constant number of sequence splits and merges.

2. Calculate the weight of a group

Let $$$z$$$ be the number of zeros in the input string. These are exactly the optional elements when choosing a superset.

For a group $$$G$$$, define its weight $$$w(G)$$$ as the probability that the group is occupied when choosing a uniformly random superset.

There are two cases:

• If the group contains at least one mandatory element, meaning some original position $$$i$$$ with $$$s[i]=\texttt{'1'}$$$, it is always occupied. Its weight is $$$1$$$.
• Otherwise, all $$$|G|$$$ elements are optional. The group is empty only when none of them is selected. Hence its weight is

Different groups contain disjoint sets of original elements, so their occupancy events are independent.

Consequently, the number of supersets in which the first $$$k$$$ groups are all occupied is

Here, $$$2^z$$$ is the total number of supersets.

3. Express MEX using prefix products

The MEX is the number of consecutive occupied groups starting from group $$$0$$$.

Equivalently, it can be written as

Taking the sum over all supersets, the contribution of the current group sequence becomes

Define

where $$$q$$$ is the current number of groups.

Then the contribution of this state over all supersets is simply

We add pref after every transformation and multiply the final accumulated answer by $$$2^z$$$.

All calculations are performed modulo $$$10^9+7$$$.

4. Maintain the aggregate with a monoid

For a sequence $$$A$$$, maintain two values:

• $$$\operatorname{prod}(A)$$$: the product of all weights in $$$A$$$.
• $$$\operatorname{pref}(A)$$$: the sum of all prefix products in $$$A$$$.

For two consecutive sequences $$$A$$$ and $$$B$$$,

and

The second identity holds because every non-empty prefix contained in $$$B$$$ is preceded by the entire sequence $$$A$$$, so its product gains a factor of $$$\operatorname{prod}(A)$$$.

The identity aggregate is

and a single group of weight $$$w$$$ has aggregate

These operations define a monoid, so the aggregate can be maintained in an implicit treap with the usual pull() operation.

Each treap node stores the information about one group:

• len: the number of original elements in the group.
• fixed: whether the group contains a mandatory element.
• weight: the group's occupancy probability.

When two groups merge, their lengths are added, their fixed flags are ORed, and the new weight is recalculated from this information.

5. Perform each transformation

For a current sequence of $$$m+1$$$ groups, split the treap into:

• first: $$$G[0]$$$,
• mid: $$$G[1],\ldots,G[m-2]$$$,
• pen: $$$G[m-1]$$$,
• last: $$$G[m]$$$.

Create a new group by merging first and last, then build the sequence

This is exactly

For $$$m=1$$$, merge the only two groups directly.

After rebuilding the treap, its root aggregate gives the pref value for the new state. Add this value to the answer.

Each transformation uses only a constant number of implicit-treap operations, so it takes $$$O(\log n)$$$ expected time.

#include <bits/stdc++.h>
#include <cassert>

using namespace std;
namespace wala {

template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vector<T>>;
using pii = pair<int,int>;
using vi = vector<int>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

template<class T> int sz(const T& x) { return int(x.size()); }
template<class T> void ckmin(T& a,const T& b) { if(b<a) a=b; }
template<class T> void ckmax(T& a,const T& b) { if(b>a) a=b; }

inline int floor_log2(unsigned x) {
	return x ? 31-__builtin_clz(x) : -1;
}
inline int ceil_log2(unsigned x) {
	return x<=1 ? 0 : floor_log2(x-1)+1;
}
inline int next_pow2(unsigned x) {
	return 1 << ceil_log2(x);
}

template<class F> struct reverse_comparator_t {
	F f;

	template<class A,class B>
	constexpr bool operator()(A&& a,B&& b) & {
		return f(forward<B>(b),forward<A>(a));
	}
	template<class A,class B>
	constexpr bool operator()(A&& a,B&& b) const& {
		return f(forward<B>(b),forward<A>(a));
	}
	template<class A,class B>
	constexpr bool operator()(A&& a,B&& b) && {
		return move(f)(forward<B>(b),forward<A>(a));
	}
	template<class A,class B>
	constexpr bool operator()(A&& a,B&& b) const&& {
		return move(f)(forward<B>(b),forward<A>(a));
	}
};

template<class F>
constexpr auto reverse_comparator(F&& f) {
	return reverse_comparator_t<decay_t<F>>{forward<F>(f)};
}

template<int MOD> struct modint {
	int v=0;

	modint()=default;
	template<class T> modint(T x) {
		ll y=(ll)x%MOD;
		if(y<0) y+=MOD;
		v=int(y);
	}

	static constexpr int mod() { return MOD; }
	int val() const { return v; }

	modint& operator+=(const modint& o) {
		v+=o.v;
		if(v>=MOD) v-=MOD;
		return *this;
	}
	modint& operator-=(const modint& o) {
		v-=o.v;
		if(v<0) v+=MOD;
		return *this;
	}
	modint& operator*=(const modint& o) {
		v=int((ll)v*o.v%MOD);
		return *this;
	}

	friend modint operator+(modint a,const modint& b) { return a+=b; }
	friend modint operator-(modint a,const modint& b) { return a-=b; }
	friend modint operator*(modint a,const modint& b) { return a*=b; }

	modint pow(ll e) const {
		modint a=*this,r=1;
		for(;e;e>>=1,a*=a) if(e&1) r*=a;
		return r;
	}
	modint inv() const {
		assert(v);
		return pow(MOD-2);
	}
	modint& operator/=(const modint& o) { return *this*=o.inv(); }
	friend modint operator/(modint a,const modint& b) { return a/=b; }

	bool operator==(const modint& o) const { return v==o.v; }
	bool operator!=(const modint& o) const { return v!=o.v; }
};
using Mint = modint<1000000007>;

struct DSU {
	vi p,s;

	DSU(int n=0) { init(n); }

	void init(int n) {
		p.resize(n);
		iota(p.begin(),p.end(),0);
		s.assign(n,1);
	}

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

	bool unite(int a,int b) {
		a=find(a),b=find(b);
		if(a==b) return false;
		if(s[a]<s[b]) swap(a,b);
		p[b]=a;
		s[a]+=s[b];
		return true;
	}

	bool same(int a,int b) { return find(a)==find(b); }
	int size(int x) { return s[find(x)]; }
};
struct RollbackDSU {
	struct Change { int a,b,sz; };
	vi p,s;
	vector<Change> hist;

	RollbackDSU(int n=0) { init(n); }

	void init(int n) {
		p.resize(n);
		iota(p.begin(),p.end(),0);
		s.assign(n,1);
		hist.clear();
	}

	int find(int x) const {
		while(p[x]!=x) x=p[x];
		return x;
	}

	int snapshot() const { return sz(hist); }

	bool unite(int a,int b) {
		a=find(a),b=find(b);
		if(a==b) {
			hist.push_back({-1,-1,-1});
			return false;
		}
		if(s[a]<s[b]) swap(a,b);
		hist.push_back({a,b,s[a]});
		p[b]=a;
		s[a]+=s[b];
		return true;
	}

	void rollback(int snap) {
		while(sz(hist)>snap) {
			auto [a,b,old]=hist.back();
			hist.pop_back();
			if(a==-1) continue;
			p[b]=b;
			s[a]=old;
		}
	}
};

template<class T> struct FenwickTree {
	int n;
	vec<T> bit;

	FenwickTree(int n=0):n(n),bit(n+1,T()) {}

	void add(int p,T x) {
		for(++p;p<=n;p+=p&-p) bit[p]+=x;
	}

	// Sum over [0,r).
	T sum(int r) const {
		T res=T();
		for(;r;r-=r&-r) res+=bit[r];
		return res;
	}

	// Sum over [l,r).
	T query(int l,int r) const {
		return sum(r)-sum(l);
	}
};

template<class T,class Compare=less<T>> struct SparseTable {
	int n=0;
	vec<vec<T>> st;
	Compare cmp;

	SparseTable() {}

	explicit SparseTable(const vec<T>& a,Compare c=Compare())
		:n(sz(a)),cmp(c) {
		if(!n) return;
		int lg=32-__builtin_clz((unsigned)n);
		st.assign(lg,vec<T>(n));
		st[0]=a;

		for(int j=1;j<lg;j++)
			for(int i=0;i+(1<<j)<=n;i++) {
				const T& x=st[j-1][i];
				const T& y=st[j-1][i+(1<<(j-1))];
				st[j][i]=cmp(x,y)?x:y;
			}
	}

	// Inclusive range [l,r].
	T query(int l,int r) const {
		assert(0<=l && l<=r && r<n);
		int j=floor_log2((unsigned)(r-l+1));
		const T& x=st[j][l];
		const T& y=st[j][r-(1<<j)+1];
		return cmp(x,y)?x:y;
	}
};

template<class T> using RangeMinQuery=SparseTable<T,less<T>>;
template<class T> using RangeMaxQuery=SparseTable<T,greater<T>>;

struct CartesianTree {
	struct Node {
		int p=-1;
		array<int,2> c={-1,-1};
	};

	vec<Node> nodes;
	int root=-1;

	template<class T,class Compare=less<T>>
	static CartesianTree build_min_tree(const vec<T>& a,Compare cmp=Compare()) {
		CartesianTree res;
		int n=sz(a);
		res.nodes.resize(n);
		vi st;

		for(int i=0;i<n;i++) {
			int last=-1;
			while(!st.empty() && cmp(a[i],a[st.back()])) {
				last=st.back();
				st.pop_back();
			}

			if(!st.empty()) {
				res.nodes[st.back()].c[1]=i;
				res.nodes[i].p=st.back();
			}
			if(last!=-1) {
				res.nodes[i].c[0]=last;
				res.nodes[last].p=i;
			}
			st.push_back(i);
		}

		if(!st.empty()) res.root=st.front();
		return res;
	}

	template<class T,class Compare=less<T>>
	static CartesianTree build_max_tree(const vec<T>& a,Compare cmp=Compare()) {
		return build_min_tree(a,reverse_comparator(cmp));
	}
};

template<class T,class Op> struct SegmentTree {
	int n=0,S=1;
	T id{};
	Op op;
	vec<T> t;

	SegmentTree() {}

	SegmentTree(const vec<T>& a,T id_,Op op_=Op()) {
		build(a,id_,op_);
	}

	void build(const vec<T>& a,T id_,Op op_=Op()) {
		n=sz(a),id=id_,op=op_;
		S=1;
		while(S<n) S<<=1;
		t.assign(2*S,id);
		for(int i=0;i<n;i++) t[S+i]=a[i];
		for(int i=S-1;i;i--) t[i]=op(t[i<<1],t[i<<1|1]);
	}

	void set(int p,T x) {
		for(t[p+=S]=x,p>>=1;p;p>>=1)
			t[p]=op(t[p<<1],t[p<<1|1]);
	}

	// Half-open range [l,r).
	T query(int l,int r) const {
		T a=id,b=id;
		for(l+=S,r+=S;l<r;l>>=1,r>>=1) {
			if(l&1) a=op(a,t[l++]);
			if(r&1) b=op(t[--r],b);
		}
		return op(a,b);
	}
};

struct Graph {
	struct Edge {
		int to,id;
	};

	int n;
	vvec<Edge> adj;
	int edges=0;

	Graph(int n=0):n(n),adj(n) {}

	void add_edge(int u,int v) {
		adj[u].push_back({v,edges});
		adj[v].push_back({u,edges++});
	}

	vi bfs(int root) const {
		vi d(n,-1);
		queue<int> q;
		q.push(root);
		d[root]=0;

		while(!q.empty()) {
			int u=q.front(); q.pop();
			for(auto e:adj[u]) if(d[e.to]==-1) {
				d[e.to]=d[u]+1;
				q.push(e.to);
			}
		}
		return d;
	}
};

struct BinaryLifting {
	int n=0,LOG=0;
	vvec<int> up;
	vi depth;

	void build(const vvec<int>& adj,int root) {
		n=sz(adj);
		LOG=32-__builtin_clz((unsigned)n);
		up.assign(LOG,vi(n,root));
		depth.assign(n,0);

		vi par(n,-1),order={root};
		par[root]=root;

		for(int i=0;i<sz(order);i++) {
			int u=order[i];
			for(int v:adj[u]) if(v!=par[u]) {
				par[v]=u;
				depth[v]=depth[u]+1;
				order.push_back(v);
			}
		}

		up[0]=par;
		for(int j=1;j<LOG;j++)
			for(int i=0;i<n;i++)
				up[j][i]=up[j-1][up[j-1][i]];
	}

	int jump(int u,int k) const {
		for(int j=0;j<LOG;j++) if(k>>j&1) u=up[j][u];
		return u;
	}

	int lca(int u,int v) const {
		if(depth[u]<depth[v]) swap(u,v);
		u=jump(u,depth[u]-depth[v]);
		if(u==v) return u;

		for(int j=LOG-1;j>=0;j--)
			if(up[j][u]!=up[j][v]) u=up[j][u],v=up[j][v];
		return up[0][u];
	}

	int dist(int u,int v) const {
		int w=lca(u,v);
		return depth[u]+depth[v]-2*depth[w];
	}
};

inline vi prefix_function(const string& s) {
	int n=sz(s);
	vi pi(n);

	for(int i=1;i<n;i++) {
		int j=pi[i-1];
		while(j && s[i]!=s[j]) j=pi[j-1];
		if(s[i]==s[j]) j++;
		pi[i]=j;
	}
	return pi;
}

inline vi z_function(const string& s) {
	int n=sz(s);
	vi z(n);
	for(int i=1,l=0,r=0;i<n;i++) {
		if(i<r) z[i]=min(r-i,z[i-l]);
		while(i+z[i]<n && s[z[i]]==s[i+z[i]]) z[i]++;
		if(i+z[i]>r) l=i,r=i+z[i];
	}
	if(n) z[0]=n;
	return z;
}

template<class Value,class Monoid> class ImplicitTreap {
public:
	using aggregate_type=typename Monoid::value_type;

	struct Node {
		Value val;
		aggregate_type agg;
		uint64_t pri;
		int l=-1,r=-1,sz=1;

		Node(Value v,uint64_t p)
			:val(move(v)),agg(Monoid::lift(val)),pri(p) {}
	};

private:
	vec<Node> t;
	mt19937_64 rng;

	int node_size(int x) const {
		return x==-1 ? 0 : t[x].sz;
	}

	aggregate_type aggregate(int x) const {
		return x==-1 ? Monoid::identity() : t[x].agg;
	}

	void pull(int x) {
		Node& u=t[x];
		u.sz=1+node_size(u.l)+node_size(u.r);
		u.agg=Monoid::combine(
			Monoid::combine(aggregate(u.l),Monoid::lift(u.val)),
			aggregate(u.r)
		);
	}

public:
	explicit ImplicitTreap(int reserve=0,uint64_t seed=712367821):rng(seed) {
		t.reserve(reserve);
	}

	int size(int root) const { return node_size(root); }

	int add(Value v) {
		t.emplace_back(move(v),rng());
		return sz(t)-1;
	}

	const Value& value(int x) const {
		assert(x!=-1);
		return t[x].val;
	}

	aggregate_type get_aggregate(int x) const {
		return aggregate(x);
	}

	int merge(int a,int b) {
		if(a==-1) return b;
		if(b==-1) return a;

		if(t[a].pri>t[b].pri) {
			t[a].r=merge(t[a].r,b);
			pull(a);
			return a;
		}

		t[b].l=merge(a,t[b].l);
		pull(b);
		return b;
	}

	// First k elements, remaining elements.
	pair<int,int> split(int x,int k) {
		if(x==-1) return {-1,-1};
		assert(0<=k && k<=node_size(x));

		if(node_size(t[x].l)>=k) {
			auto [a,b]=split(t[x].l,k);
			t[x].l=b;
			pull(x);
			return {a,x};
		}

		auto [a,b]=split(t[x].r,k-node_size(t[x].l)-1);
		t[x].r=a;
		pull(x);
		return {x,b};
	}
};

struct Group {
	int len=0;
	bool fixed=false;
	Mint weight=0;
};

struct PrefixProductMonoid {
	struct value_type {
		Mint prod,pref;
	};

	static value_type identity() {
		return {1,0};
	}

	static value_type lift(const Group& g) {
		return {g.weight,g.weight};
	}

	// pref(A + B) = pref(A) + prod(A) * pref(B).
	static value_type combine(value_type a,value_type b) {
		return {a.prod*b.prod,a.pref+a.prod*b.pref};
	}
};

using GroupTreap=ImplicitTreap<Group,PrefixProductMonoid>;

} // namespace wala

int main() {
	ios_base::sync_with_stdio(false),cin.tie(nullptr);

	using wala::Group;
	using wala::GroupTreap;
	using wala::Mint;

	int T; cin>>T;
	while(T--) {
		int n; cin>>n;
		string s; cin>>s;

		int zeros=count(s.begin(),s.end(),'0');

		vector<Mint> invpow(n+1),pow2(n+1);
		invpow[0]=pow2[0]=1;
		Mint inv2=Mint(2).inv();

		for(int i=1;i<=n;i++) {
			invpow[i]=invpow[i-1]*inv2;
			pow2[i]=pow2[i-1]*2;
		}

		auto make_group=[&](int len,bool fixed) -> Group {
			return {len,fixed,fixed ? Mint(1) : Mint(1)-invpow[len]};
		};

		GroupTreap tr(2*n);

		auto join_group=[&](int x,int y) -> Group {
			const Group& a=tr.value(x);
			const Group& b=tr.value(y);
			return make_group(a.len+b.len,a.fixed||b.fixed);
		};

		int root=-1;
		for(int i=0;i<n;i++)
			root=tr.merge(root,tr.add(make_group(1,s[i]=='1')));

		Mint ans=0;

		for(int m=n-1;m>=1;m--) {
			auto [first,rest]=tr.split(root,1);

			if(m==1) {
				// the final two groups collapse into one
				root=tr.add(join_group(first,rest));
			} else {
				auto [mid,tail]=tr.split(rest,m-2);
				auto [pen,last]=tr.split(tail,1);

				// new order: pen, (first + last), mid
				int merged=tr.add(join_group(first,last));
				root=tr.merge(tr.merge(pen,merged),mid);
			}

			assert(tr.size(root)==m);
			ans+=tr.get_aggregate(root).pref;
		}

		ans*=pow2[zeros];
		cout<<ans.val()<<'\n';
	} return 0;
}

Complexity

Let $$$N$$$ be the length of the input string.

• Building the initial implicit treap takes $$$O(N\log N)$$$ expected time.
• There are $$$N-1$$$ transformations.
• Each transformation performs a constant number of treap splits and merges, taking $$$O(\log N)$$$ expected time.
• The treap stores $$$O(N)$$$ nodes. Old nodes are not reused, but at most one new node is created per transformation, so the total number of allocated nodes remains $$$O(N)$$$.

Therefore, the total complexity per test case is:

• Time: $$$O(N\log N)$$$ expected.
• Space: $$$O(N)$$$.

The additional local-library utilities are not instantiated by this solution and do not add runtime work.