_I used AI to fix my grammar, so this blog might look like it was written by AI. You can read the Chinese version of this blog [here](https://www.luogu.com.cn/article/3v6yitu4)._↵
↵
Upd 2026.08.30: Replaced with a cleaner proof. Thanks to [user:PhirainEX,2026-08-30] for the inspiration!↵
↵
This is an alternative solution to [problem:2241F], which differs from the editorial.↵
↵
Obviously, if the remaining sequence length is $\le 1$, the number of inversions is $0$, making it a P-state (a losing state for the current player). Now, let's consider the following three states:↵
↵
- If the initial number of inversions is odd, Alice can simply remove the entire sequence, leaving an empty sequence. Thus, this is an N-state (a winning state for the current player), and Alice wins.↵
- If the initial number of inversions is even, and there exists an index $i$ such that the number of inversions becomes odd after removing $s_i$ (which is equivalent to saying $s_i$ contributes an odd number of inversions), Alice can remove everything except $s_i$. This leaves a sequence of length $1$, so this is also an N-state, and Alice wins.↵
- If neither of the above conditions is met, we can make an observation and guess that Bob wins (P-state).↵
↵
<spoiler summary="Proof">↵
Let $\operatorname{inv}(s)$ denote the number of inversions in string $s$. Suppose the initial state is in state three. Alice chooses to remove subsequence $a$, leaving subsequence $b$. Since $s$ is in state three, any $0$ in $s$ has an even number of 1s before it, and any $1$ has an even number of 0s after it. According to the problem constraints, we must have $\operatorname{inv}(a) \equiv 1 \pmod 2$. We need to prove that subsequence $b$ cannot be in state three.↵
↵
Let $\operatorname{inv}(a,b)$ denote the number of cross-inversions between $a$ and $b$. Cross-inversions fall into two categories:↵
↵
- A $1$ is in $a$ and a $0$ is in $b$, with the $1$ appearing before the $0$.↵
- A $1$ is in $b$ and a $0$ is in $a$,↵
Obviously, an inversion consists of a $1$ and a $0$ that comes after it. The reduction in the total number of inversions after an operation equals the number of inversions where at least one of its elements ($0$ or $1$) is deleted. By the Inclusion-Exclusion Principle, this equals (inversions with deleted $1$s) + (inversions with deleted $0$s) - (inversions with bothe $10$ appearing before the $0$.↵
↵
When splitting $s$ into $a$ and $b$, the total number of inversions satisfies $\operatorname{inv}(s)=\operatorname{inv}(a)+\operatorname{inv}(b)+\operatorname{inv}(a,b)$.↵
↵
We will use proof by contradiction. Assume that $b$ is also in state three. Let's analyze the parity of $\operatorname{inv}(a,b)$:↵
↵
- For the first type of cross-nd $1$ deleted).↵
↵
Let's analyze the parity of these three terms:↵
↵
- Inversions with deleted $1$s: This is equal to the sum of inversion,s consider each $0$ in $b$: in the original sequence $s$, it has an even number of $1$s before it. In $b$, stributed by each deleted $1$ in the chosen subsequence. Since $bs$ is also assumed to be in state three, it also has an even number of $1$s before it. Since subtracting two even numbers yields anin state three, each $s_i$ contributes an even number of inversions. Thus, this term is the sum of several even numbers, the number of $1$s before it that belong to $a$ must also be even. Summing these even counts across all $0$s in $b$ still resultswhich is even.↵
- Inversions with deleted $0$s: By the same logic, this term ins anlso even number.↵
- For the second type of cross-i.↵
- Inversion, consider eacs with both $10$ in $b$: in the original sequence $s$, it has an even number of $0$s after it. In $b$, since $b$ is in state three, it also has an even number of $0$s after it. By the same logic, the number of $0$s after it that belong to $a$ must be even. Summing these up across all $1$s in $b$ gives an even number.↵
↵
Since both types of cross-inversions have an even count, their sum, $\operatorname{inv}(a,b)$, must be even.↵
↵
Substituting these parities back into our formula:↵
↵
$$\begin{aligned}↵
\operatorname{inv}(s)&=\operatorname{inv}(a)+\operatorname{inv}(b)+\operatorname{inv}(a,b)\\↵
0&\equiv1+\operatorname{inv}(b)+0\pmod2\\↵
\operatorname{inv}(b)&\equiv1\pmod2↵
\end{aligned}$$↵
↵
This implies that $\operatorname{inv}(b)$ must be odd, meaning $b$ transitions into state one. This contradicts our assumption that $b$ is in state three. Therefore, subsequence $b$ cannot be in state three, meaning any move Alice makes will leave the sequence in either state one or state two. Thus, if $s$ starts in state three, Bob always wins.and $1$ deleted: This is simply the number of inversions within the chosen deleted subsequence itself. According to the problem statement, this must be odd.↵
↵
In conclusion, the reduction in the total number of inversions after Alice's move must be odd. Since the total number of inversions in state three is initially even, the sequence will have an odd number of inversions after her move. This guarantees that Bob receives state one (an N-state), so he can immediately win by removing the entire sequence.↵
↵
</spoiler>↵
↵
Since we are dealing with a $01$-string, maintaining the number of inversions only requires prefix sums, so data structures like a Fenwick tree are unnecessary.↵
↵
<spoiler summary="Implementation">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
const int N = 200005;↵
int _, n, sum[N], tot;↵
string s;↵
bool flag;↵
signed main() {↵
cin >> _;↵
while (_--) {↵
cin >> n >> s;↵
s = " " + s;↵
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] ^ 48);↵
tot = 0;↵
for (int i = 1; i <= n; i++) if (s[i] == '0') tot += sum[i];↵
if (tot & 1) {↵
puts("Alice");↵
continue;↵
}↵
flag = 0;↵
for (int i = 1; i <= n; i++) {↵
if (s[i] == '0' && (sum[i] & 1)) {↵
flag = 1;↵
break;↵
} else if (s[i] == '1' && ((n - i - sum[n] + sum[i]) & 1)) {↵
flag = 1;↵
break;↵
}↵
}↵
puts(flag ? "Alice" : "Bob");↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
↵
Upd 2026.08.30: Replaced with a cleaner proof. Thanks to [user:PhirainEX,2026-08-30] for the inspiration!↵
↵
This is an alternative solution to [problem:2241F], which differs from the editorial.↵
↵
Obviously, if the remaining sequence length is $\le 1$, the number of inversions is $0$, making it a P-state (a losing state for the current player). Now, let's consider the following three states:↵
↵
- If the initial number of inversions is odd, Alice can simply remove the entire sequence, leaving an empty sequence. Thus, this is an N-state (a winning state for the current player), and Alice wins.↵
- If the initial number of inversions is even, and there exists an index $i$ such that the number of inversions becomes odd after removing $s_i$ (which is equivalent to saying $s_i$ contributes an odd number of inversions), Alice can remove everything except $s_i$. This leaves a sequence of length $1$, so this is also an N-state, and Alice wins.↵
- If neither of the above conditions is met, we can make an observation and guess that Bob wins (P-state).↵
↵
<spoiler summary="Proof">↵
↵
Let $\operatorname{inv}(a,b)$ denote the number of cross-inversions between $a$ and $b$. Cross-inversions fall into two categories:↵
↵
- A $1$ is in $a$ and a $0$ is in $b$, with the $1$ appearing before the $0$.↵
- A $1$ is in $b$ and a $0$ is in $a$,
Obviously, an inversion consists of a $1$ and a $0$ that comes after it. The reduction in the total number of inversions after an operation equals the number of inversions where at least one of its elements ($0$ or $1$) is deleted. By the Inclusion-Exclusion Principle, this equals (inversions with deleted $1$s) + (inversions with deleted $0$s) - (inversions with both
↵
When splitting $s$ into $a$ and $b$, the total number of inversions satisfies $\operatorname{inv}(s)=\operatorname{inv}(a)+\operatorname{inv}(b)+\operatorname{inv}(a,b)$.↵
↵
We will use proof by contradiction. Assume that $b$ is also in state three. Let's analyze the parity of $\operatorname{inv}(a,b)$:↵
↵
- For the first type of cross-
↵
Let's analyze the parity of these three terms:↵
↵
- Inversions with deleted $1$s: This is equal to the sum of inversion
- Inversions with deleted $0$s: By the same logic, this term i
- For the second type of cross-i
- Inversion
↵
Since both types of cross-inversions have an even count, their sum, $\operatorname{inv}(a,b)$, must be even.↵
↵
Substituting these parities back into our formula:↵
↵
$$\begin{aligned}↵
\operatorname{inv}(s)&=\operatorname{inv}(a)+\operatorname{inv}(b)+\operatorname{inv}(a,b)\\↵
0&\equiv1+\operatorname{inv}(b)+0\pmod2\\↵
\operatorname{inv}(b)&\equiv1\pmod2↵
\end{aligned}$$↵
↵
This implies that $\operatorname{inv}(b)$ must be odd, meaning $b$ transitions into state one. This contradicts our assumption that $b$ is in state three. Therefore, subsequence $b$ cannot be in state three, meaning any move Alice makes will leave the sequence in either state one or state two. Thus, if $s$ starts in state three, Bob always wins.
↵
In conclusion, the reduction in the total number of inversions after Alice's move must be odd. Since the total number of inversions in state three is initially even, the sequence will have an odd number of inversions after her move. This guarantees that Bob receives state one (an N-state), so he can immediately win by removing the entire sequence.↵
↵
</spoiler>↵
↵
Since we are dealing with a $01$-string, maintaining the number of inversions only requires prefix sums, so data structures like a Fenwick tree are unnecessary.↵
↵
<spoiler summary="Implementation">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
const int N = 200005;↵
int _, n, sum[N], tot;↵
string s;↵
bool flag;↵
signed main() {↵
cin >> _;↵
while (_--) {↵
cin >> n >> s;↵
s = " " + s;↵
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] ^ 48);↵
tot = 0;↵
for (int i = 1; i <= n; i++) if (s[i] == '0') tot += sum[i];↵
if (tot & 1) {↵
puts("Alice");↵
continue;↵
}↵
flag = 0;↵
for (int i = 1; i <= n; i++) {↵
if (s[i] == '0' && (sum[i] & 1)) {↵
flag = 1;↵
break;↵
} else if (s[i] == '1' && ((n - i - sum[n] + sum[i]) & 1)) {↵
flag = 1;↵
break;↵
}↵
}↵
puts(flag ? "Alice" : "Bob");↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
