You are allowed to use intermediate vertices in your sequence. Does it ever actually help? For any three vertices $$$a$$$, $$$b$$$, $$$c$$$, what is the relationship between $$$c(a,b) + c(b,c)$$$ and $$$c(a,c)$$$? Recall that for non-negative integers, $$$x + y \geq x \oplus y$$$.

Since, $$$c(a,b) + c(b,c) \geq c(a,b) \oplus c(b,c)$$$, Splitting the path doesn't minimize the distance at all. Hence $$$d(u,v) = c(u,v)$$$ always.

Since $$$d(u,v) = c(u,v)$$$ always, we can maintain a running mask $$$M$$$ (XOR of all Type 1 updates so far). A path with $$$\ell$$$ edges has its XOR-distance changed by only is $$$\ell$$$ is odd, flipping their XOR-distance by $$$M$$$, depending only on the running XOR of Type 1 queries so far. Can you precompute something per vertex that makes answering queries $$$O(30)$$$?

Observation 1: Intermediate jumps never help.

For any three vertices $$$a$$$, $$$b$$$, $$$c$$$:

since $$$x + y \geq x \oplus y$$$ for all non-negative integers. Therefore any intermediate vertex only increases the total cost, so $$$d(u,v) = c(u,v)$$$ always.

Observation 2: Effect of the running mask.

Maintain a running mask $$$M$$$ (of Type 1 queries), updated in $$$O(1)$$$ per type-1 query. A path with $$$\ell$$$ edges has its XOR-distance changed only if $$$\ell$$$ is odd, flipping their XOR-distance by exactly $$$M$$$.

Precomputation.

For each vertex $$$s$$$ and each bit $$$b$$$, store four counts using rerooting DP in $$$O(30n)$$$:

• $$$even[s][b][0/1]$$$ = # vertices reachable from $$$s$$$ via an even-length path with bit $$$b$$$ of XOR-distance $$$= 0$$$ or $$$1$$$
• $$$odd[s][b][0/1]$$$ = same but for odd-length paths

When merging a child $$$v$$$ into $$$u$$$ via an edge of weight $$$w$$$, extending any path from $$$v$$$ through this edge to $$$u$$$ does two things: the path length parity flips (odd $$$\leftrightarrow$$$ even), and the XOR-distance gets XOR'd with $$$w$$$, so if bit $$$b$$$ of $$$w$$$ is $$$1$$$ the bit flips, otherwise it stays.

If bit $$$b$$$ of $$$w$$$ is $$$1$$$:

Similar Transitions occur if bit $$$b$$$ of $$$w$$$ is $$$0$$$

We can use a standard DFS pass to build up these values over the subtrees. And a rerooting pass to add the upward contribution using the same transitions.

For $$$type-1$$$ queries we can maintain a running XOR of the previous $$$type-1$$$ updates

For $$$type-2$$$ queries:

For each bit $$$b$$$:

• Even-length path vertices are unaffected by $$$M$$$ $$$\to$$$ contribute $$$even[s][b][1]$$$ vertices with bit $$$b$$$ set.
• Odd-length path vertices have bit $$$b$$$ of their distance flipped iff bit $$$b$$$ of $$$M$$$ is $$$1$$$ $$$\to$$$ contribute $$$odd[s][b][0]$$$, else $$$odd[s][b][1]$$$.

The answer is $$$\displaystyle\sum_{b=0}^{29} 2^b \cdot cnt_b$$$, computed in $$$O(30)$$$.

Complexity: $$$O(30n)$$$ precomputation, $$$O(1)$$$ per type-1 query, $$$O(30)$$$ per type-2 query.

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.

The problem can be modeled into a directed graph, draw out some valid graphs for small n, what kind of graphs are these?

If you know answer for $$$i - 1$$$ players, can you relate it to find answer for $$$i$$$ players?

Lets reword the problem first. The problem essentially boils down to the following statement:

You have a directed graph consisting of $$$n$$$ nodes, where every node has an out-degree of $$$1$$$ and except one node every other node has in-degree $$$ \gt 0$$$. There are no self-loops in the graph. We have to count total number of such graphs.

From the above observations, the graph splits into $$$X$$$ $$$(X \ge 1)$$$ disjoint components. Among these, $$$X - 1$$$ components are simple cycles, while the remaining component contains a cycle along with a tail that eventually merges into a node within that component.

To help you visualize this, for $$$X = 2$$$ one such example is following:

Let $$$f(n)$$$ denote the total valid graphs for given $$$n$$$ nodes. Lets call the node with no ingoing edge as bad node.

Lets say there's some valid graph for $$$n-1$$$ nodes we can add one additional node and if the outgoing edge of it points towards the existing bad node, the new resulting graph contributes to $$$f(n)$$$.

Since we can choose any of the $$$n$$$ nodes as the new bad node:

$$$f(n) \supset n \cdot f(n - 1)$$$

But this alone is not it, there's one more case wherein the $$$n - 1$$$ nodes forms a set of disjoint directed cycles and the bad node points to any of the remaining $$$n - 1$$$ nodes.

Visually the following depicts this case:

As you can see, the bad node can point to any of other $$$n - 1$$$ nodes and the resulting graph would be valid.

There are $$$n$$$ ways to choose the bad node, $$$n - 1$$$ ways to choose the node to which it points, lets say the total number of ways to form a set of disjoint cyclic graph from $$$n - 1$$$ nodes be $$$d(n - 1)$$$.

So in overall,

$$$f(n) = n * f(n - 1) + n * (n - 1) * d(n - 1)$$$

We only need to find $$$d(n - 1)$$$ or say $$$d(n)$$$.

To find $$$d(n)$$$, let us consider one example of disjoint cyclic graph formed using n nodes, since each of $$$n$$$ node has exactly 1 ingoing edge, we will depict the graph with the help of an array $$$A$$$ of size $$$n$$$ such that there's an edge from $$$A[i]$$$ to $$$i$$$.

Since there are no self loops in this graph, $$$A[i] \ne i$$$,

With the above condition in mind, $$$d(n)$$$ = total permutation of $$$A = [1, 2, 3, \dots, n]$$$ such that $$$A[i] \ne i$$$.

The above is also known as derangement of $$$n$$$.

Lets say $$$A[i] = 1$$$ for some $$$1 \lt i \le n$$$. Now the element $$$i$$$ in the permutation has two choices:

1. Go to position $$$1$$$

2. Go to position other than $$$1$$$

In the first case, we have essentially swapped out places for element $$$1$$$ and element $$$i$$$ in the sorted permutation and the remaining $$$n - 2$$$ elements have to ensure to re-arrange themselves such that $$$A[j] \ne j$$$, this is nothing but $$$d(n - 2)$$$.

In the second case, we have two restrictions, $$$A[j] \ne j$$$ and $$$A[1] \ne i$$$, since for each value $$$ \gt 1$$$, we have exactly one distinct restricted index, this is nothing but $$$d(n - 1)$$$.

Since we can choose the index $$$i$$$ in $$$n - 1$$$ ways,

$$$d(n) = (n - 1) * (d(n - 1) + d(n - 2))$$$

So we have finally arrived at two recursive relations

$$$d(n) = (n - 1) * (d(n - 1) + d(n - 2))$$$

with the base case being $$$d(1) = 0$$$, $$$d(2) = 1$$$.

and

$$$f(n) = n * f(n - 1) + n * (n - 1) * d(n - 1)$$$, for $$$n \gt 2$$$

with the base case being $$$f(2) = 0$$$.

Since $$$N \le 10^6$$$, you can precompute $$$f(n)$$$ as well as $$$d(n)$$$ in linear time and just output $$$f(n)$$$ for the input $$$n$$$.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int N = 1e6 + 69;
vector<ll> f(N), d(N);
 
const int MOD = 998244353;
 
void precompute() {
    d[1] = 0;
    d[2] = 1;
 
    for(ll i = 3; i < N; i++) {
        f[i] = ((f[i - 1] * i) % MOD + (((i * (i - 1)) % MOD) * d[i - 1]) % MOD) % MOD;
        d[i] = ((i - 1) * (d[i - 1] + d[i - 2]) % MOD);
    }
}
 
void solution(){
    int n;
    cin >> n;
    cout << f[n] << endl;    
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
#ifdef PenguinsAreCool
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("debug.txt","w",stderr);
#endif
    precompute();
    int tt = 1;
    cin >> tt;
 
    while(tt--){
        solution();
    }
}

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$$$