_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)._↵
↵
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$, with the $1$ 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-inversion, consider each $0$ in $b$: in the original sequence $s$, it has an even number of $1$s before it. In $b$, since $b$ 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 an even number, 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 results in an even number.↵
- For the second type of cross-inversion, consider each $1$ 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.↵
</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>↵
↵
↵
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$, with the $1$ 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-inversion, consider each $0$ in $b$: in the original sequence $s$, it has an even number of $1$s before it. In $b$, since $b$ 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 an even number, 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 results in an even number.↵
- For the second type of cross-inversion, consider each $1$ 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.↵
</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>↵
↵
