Note that in each move, a player must choose a maximal block comprising the same element.

If all the elements are distinct, the answer will be independent of the rearrangement. What happens if there is at least one duplicate?

Note that in each move, a player must choose a maximal block comprising the same element.

If all the elements are distinct, the answer will be independent of the rearrangement. If $$$n$$$ is odd, Alice wins, and if $$$n$$$ is even, Bob wins.

Otherwise, there is at least one duplicate. Let the distinct elements in the array be $$$x_1, x_2, \ldots, x_m$$$ and let $$$X_i$$$ denote a block of $$$x_i$$$s. For simplicity, let's assume $$$x_1$$$ occurs at least $$$2$$$ times in the array $$$a$$$. Now, Alice can always guarantee a win with the following strategy:

• $$$m$$$ is odd: Rearrange the array to $$$[X_1, X_2, \ldots, X_m]$$$ and remove any block on her first move.
• $$$m$$$ is even: Rearrange the array to $$$[X_1, X_2, \ldots, X_m, X_1]$$$ and remove the last block on her first move.

Thus, Bob can win if and only if $$$n$$$ is even and all the elements are distinct.

Who wins when all elements of $$$a$$$ are equal?

Who wins when $$$a = [1, 1, 1, \dots, 1, x]$$$ where $$$x \gt 1$$$?

How can this configuration be forced during the game?

Let $$$g = \gcd(a_1, a_2, \dots, a_n)$$$.

Observe that dividing all elements by $$$g$$$ does not affect the game, since all gcd relations are preserved up to scaling. Hence, without loss of generality, we may assume $$$\gcd(a_1, a_2, \dots, a_n) = 1$$$.

Case 1: All elements are equal to $$$1$$$.

In this case, no valid move exists, since for any subsequence, all elements are equal to its gcd. Hence, Alice cannot make a move and therefore wins.

Case 2: The array is of the form $$$a = [1, 1, \dots, 1, x]$$$ where $$$x \gt 1$$$.

Any valid move must include the element $$$x$$$, since otherwise the subsequence consists only of $$$1$$$s and is invalid. If $$$x$$$ is included, the gcd of the chosen subsequence is $$$1$$$, and all selected elements become $$$1$$$. Thus, after one move, the array becomes identically $$$1$$$.

Therefore, the player making this move leaves no valid moves for the opponent. Hence, Alice loses and Bob wins.

Case 3: $$$n = 2$$$ and the array is not covered by the above cases.

Since $$$\gcd(a_1, a_2) = 1$$$, the only valid move is to select both elements, after which the array becomes $$$[1,1]$$$. This reduces the game to Case 1, so Bob wins.

Case 4: All remaining cases.

Consider all subsequences of size $$$n-1$$$. We claim that if there exists at least one such subsequence with gcd equal to $$$1$$$, then Alice wins; otherwise, Bob wins.

Conclusion:

• If all elements are $$$1$$$, Alice wins.
• Else if the array is of the form $$$[1, 1, \dots, 1, x]$$$, Bob wins.
• Else if $$$n = 2$$$, Bob wins.
• Otherwise, check if there exists a subsequence of size $$$n-1$$$ with gcd $$$1$$$:
• If yes, Alice wins.
• Otherwise, Bob wins.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
 
void solve() {
    ll n;
    cin >> n;

    vector<ll> a(n);
    for (ll i=0; i<n; i++) cin >> a[i];
    ll g = 0;
    for (ll i=0; i<n; i++) {
        g = gcd(g, a[i]);
    }

    for (ll i=0; i<n; i++) a[i] /= g;

    if (n == 2) {
        if (a[0] == a[1]) {
            cout << "Alice" << endl;
        } else {
            cout << "Bob" << endl;
        }

        return;
    }

    ll one_cnt = 0;;
    for (ll i=0; i<n; i++) if (a[i] == 1) one_cnt++;

    if (one_cnt == n) {
        cout << "Alice" << endl;
        return;
    } else if (one_cnt == n-1) {
        cout << "Bob" << endl;
        return;
    }

    vector<ll> gcd_pref(n+2);
    vector<ll> gcd_suf(n+2);
    
    for (ll i=0; i<n; i++) {
        gcd_pref[i+1] = gcd(gcd_pref[i], a[i]);
    }
    for (ll i=n-1; i>=0; i--) {
        gcd_suf[i+1] = gcd(gcd_suf[i+2], a[i]);
    }

    for (ll i=1; i<=n; i++) {
        if (gcd(gcd_pref[i-1], gcd_suf[i+1]) == 1) {
            cout << "Alice" << endl;
            return;
        }
    }

    cout << "Bob" << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    cin >> t;

    while (t--) solve();
    
    return 0;
}

Consider you have the answer of length $$$i$$$, how can you find the length of $$$i+1$$$?

You can get the answer of $$$i+1$$$ from answer of $$$i$$$ by prepending or appending a $$$0$$$ or $$$1$$$. WLOG, if we assume we prepend, in what specific cases will adding a $$$0$$$ or a $$$1$$$ actually increase the length of the longest non-decreasing subsequence?

Let $$$E_i$$$ represent the expected value of the LNDS of a string of length $$$i$$$.

Let's say we prepend a character to the start of a string of length $$$i-1$$$. If we prepend a 0, it will always contribute to the longest subsequence, giving a guaranteed $$$+1$$$ to the length.

If we prepend a 1, it will only contribute if the entire longest non-decreasing subsequence of the remaining string consists only of 1s. This gives us a new subproblem: In which cases does a string have entirely 1s as its optimal subsequence?

Consider any prefix of the string. If a prefix has more 0s than 1s, we could simply take those 0s and improve our LNDS length. Therefore, a necessary and sufficient condition for the LNDS to be entirely 1s is that for every prefix, the count of 0s is $$$\le$$$ the count of 1s.

How do we count the number of such strings? This is a classic application of Bertrand's ballot theorem (which relies on the reflection principle).

Let $$$N = i-1$$$. We want to find the number of paths of length $$$N$$$ where the number of 1s minus the number of 0s never drops below zero. The total number of paths of length $$$N$$$ that end at a difference of $$$y$$$ is $$$\binom{N}{\frac{N+y}{2}}$$$. By the reflection principle, the number of valid paths ending at $$$y$$$ that never dip below zero is $$$\binom{N}{\frac{N+y}{2}} - \binom{N}{\frac{N+y+2}{2}}$$$.

To find all valid strings, we sum this over all possible valid ending differences $$$y \ge 0$$$. Notice how the sum telescopically cancels out:

If $$$N$$$ is even ($$$y = 0, 2, 4, \dots$$$):

If $$$N$$$ is odd ($$$y = 1, 3, 5, \dots$$$):

So we can say number of valid strings are: $$$\binom{N}{\lfloor N/2 \rfloor}$$$. Substituting $$$N = i-1$$$ back in, the number of valid strings is $$$\binom{i-1}{\lfloor (i-1)/2 \rfloor}$$$.

Since there are $$$2^{i-1}$$$ total possible strings of length $$$i-1$$$, the probability of getting one of these valid strings is $$$\frac{\binom{i-1}{\lfloor (i-1)/2 \rfloor}}{2^{i-1}}$$$.

This gives us this final transition:

Which simplifies to:

If we unroll this recurrence relation from $$$i = 1$$$ to $$$n$$$, the $$$\frac{1}{2}$$$ term simply adds up $$$n$$$ times. Therefore, the final expected value for a string of length $$$n$$$ can be directly computed as the sum:

#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

ll MOD;
ll bin_exp(ll a, ll b, ll mod) {
    a %= mod;
    ll ans = 1;
    while (b > 0) {
        if (b & 1) {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

ll inv(ll x) { return bin_exp(x % MOD, MOD - 2, MOD); }

void solve() {
    ll n;
    cin >> n >> MOD;
    vector<ll> fact(n + 1), invfact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    invfact[n] = inv(fact[n]);
    for (ll i = n - 1; i >= 0; i--)
        invfact[i] = (invfact[i + 1] * (i + 1)) % MOD;

    auto nCr = [&](ll n, ll r) ->ll {
        if (r < 0 || r > n)
            return 0;
        return ((((fact[n]) % MOD * invfact[r]) % MOD) * invfact[n - r]) % MOD;
        };

    ll inv2 = inv(2);
    ll cur = inv2 * inv2 % MOD;

    ll tot = inv2;
    for(int i = 1; i < n; i++){
        tot = (tot + nCr(i, i / 2) * cur % MOD) % MOD;
        cur = cur * inv2 % MOD;
    }

    tot = (tot + (n * inv(2)) % MOD) % MOD;
    cout << tot << endl;
}

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Trivially, if $$$a = b$$$, there is no valid solution. WLOG, assume $$$a \lt b$$$.

If $$$a \lt b$$$, we have $$$a \bmod b = a$$$ and $$$b \bmod a \lt a$$$.

Trivially, if $$$a = b$$$, there is no valid solution. WLOG, assume $$$a \lt b$$$.

If $$$a \lt b$$$, we have $$$a \bmod b = a$$$ and $$$b \bmod a \lt a$$$. This implies that $$$(a \bmod b) + (b \bmod a) \lt 2a$$$. From the given equation, we must have $$$a | b \lt 2a$$$, which forces the condition $$$\text{msb}(b) \le \text{msb}(a)$$$. From our assumption $$$a \lt b$$$, the condition further simplifies to $$$\text{msb}(b) = \text{msb}(a)$$$.

Note that if $$$\text{msb}(b) = \text{msb}(a)$$$, we must have $$$b \lt 2a$$$. Thus, $$$a \lt b \lt 2a$$$. This makes $$$(b \bmod a) = b - a$$$. Hence, the given equation reduces to $$$b = (a | b)$$$, $$$\text{msb}(b) = \text{msb}(a)$$$.

For counting the number of pairs, we can iterate over all possible values of $$$b$$$ from $$$1$$$ to $$$n$$$ and find the number of sub-masks of $$$b$$$ that are not more than $$$m$$$ and have the same $$$\text{msb}$$$. Now, we repeat the same process and find the number of pairs with $$$a \gt b$$$.

How many times can the prefix $$$\gcd$$$ sequence $$$x_i = \gcd(a_1,\dots,a_i)$$$ change?

It changes at most $$$O(\log A)$$$ times since each change makes it at least half.

After removing one element from a segment, what condition must the remaining $$$\gcd$$$ satisfy to become a target value after one modification?

You need:

where $$$g$$$ is the $$$\gcd$$$ after removal and $$$t$$$ is the target.

Define a function

For each index $$$i$$$, let

and define

We need to count all $$$i$$$ such that $$$f(P_i, S_i) = 1$$$.

A modification consists of changing at most one element in $$$P_i \cup S_i$$$. Observe that changing an element is equivalent to removing it and replacing it with a suitable value, hence it suffices to consider removal.

Thus, for a fixed $$$i$$$, the following cases arise:

(1) No modification:

(2) One removal in prefix: There exists $$$j \le i$$$ such that

(3) One removal in suffix: There exists $$$k \gt i$$$ such that

Hence,

Using the property that gcd values over prefixes and suffixes form at most $$$O(\log A)$$$ distinct values, we can efficiently maintain all possible gcds obtained by removing one element. Precomputing $$$x_i$$$ and $$$y_i$$$, and iterating over $$$i$$$, we check the above conditions in total $$$O(n \log A)$$$ time.

Lemma 1. (Prefix $$$\gcd$$$ changes $$$O(\log A)$$$ times)

Let $$$x_i = \gcd(a_1,\dots,a_i)$$$. Then $$$x_i$$$ takes $$$O(\log A)$$$ distinct values.

Proof.

If $$$x_{i+1} \ne x_i$$$, then $$$x_{i+1}$$$ is a proper divisor, so:

Thus after $$$k$$$ changes: $$$x_i \le A/2^k \ge 1 \Rightarrow k \le \log_2 A$$$.

Lemma 2. (Divisibility condition is sufficient and necessary)

Let $$$g = \gcd(P_i \setminus {a_j})$$$. Then one modification makes $$$\gcd(P_i)=y_i$$$ iff:

Proof.

If $$$y_i \mid g$$$, replace $$$a_j$$$ with $$$y_i$$$: $$$\gcd(g, y_i) = y_i$$$