We begin with the answer.

Consider a graph with \(2N\) vertices where vertex \(i\) has \(A_i\) written on it. Span a red edge between vertices with the same number. Also, if \(M\) is even, span a blue edge between vertices whose difference of the written numbers modulo \(M\) is \(M/2\). If there is a perfect matching using an even number of blue edges, Bob wins; otherwise, Alice wins.

Let us verify this. Below, we will only evaluate game states where it is Alice’s turn. Let us fix notations to describe a game state. Assume that the blackboard now has \(B = (B_1, B_2, \dots, B_{2k})\), and let \(S\) and \(T\) be the sum of numbers deleted by Alice and Bob, respectively. Call the graph constructed as explained above \(G\). Also, let \(d\) be \((S-T) \bmod M\).

1. The case with an odd \(M\)

This is the easier case, so let us start with it.
We can ignore the condition on blue edges since \(G\) has only red edges if \(M\) is odd. Let us do some division into cases.

1.1 A state where \(G\) has a perfect matching and \(d=0\)

Bob can win by imitating Alice, that is, deleting the same number as Alice.
One can show the validity of this inductively from the fact that Bob wins if \(G\) is empty, and the case where \(|G| \gt 0\) can be reduced to a case with two less vertices.

1.2 A state where \(G\) has a perfect matching and \(d \neq 0\)

If \(\vert G \vert = 0\), obviously Alice wins. If \(\vert G \vert \gt 0\), Alice can win by a modified imitating strategy as follows.

1. Alice arbitrarily chooses an element \(x\) in \(B\) and deletes it.
2. If Bob next deletes \(y\) such that \(y \neq x\), Alice also deletes \(y\). Repeat this until Bob deletes \(x\).
3. When Bob deletes \(x\) after repeating 2. zero or more times, the graph \(G'\) has a perfect matching, and \(d\) remains \(0\), so Alice can return to 1. and repeat the same procedure.

This strategy allows Alice to make \(\vert G \vert = 0\) while keeping \(d \neq 0\).

1.3 A state where \(G\) has no perfect matching (with any \(d\))

Assume that the blackboard now has \(B=(B_1, B_2, \dots, B_{2k})\).
We will first consider the case the size of the maximum matching in \(G\) is \(k-1\). Let \(u\) and \(v\) be the numbers written on the vertices not used in this matching.
Here, we have \(u \neq v\) and \(M \bmod 2 = 1\), so \((u - v) \bmod M\) and \((v - u) \bmod M\) are different (\(\because u-v\equiv v-u \iff 2(u-v) \equiv 0 \pmod{M}\)). Thus, at least one of \((d + u - v) \bmod{M}\) and \((d - u + v) \bmod{M}\) is non-zero. Without loss of generality, we assume \((d + u - v) \bmod{M} \neq 0\).
Here, it can be verified that Alice can win by deleting \(u\) and employing the imitating strategy in 1.2. (We will omit the details.)
In the case the size of the maximum matching in \(G\) is \(k-2\) or less, constantly deleting a number written on a vertex that does not form the matching leads to the case \(\vert \text{(the size of the maximum matching)}\vert + 1 = \vert G \vert / 2\).

2. The case with a general \(M\)

The proof in 1.3 does not hold for a general \(M\), particularly an even \(M\). For instance, when \(M = 8\) and \((u, v) = (1, 5)\), we have \(1 - 5 \equiv 5 - 1 \equiv 4 \pmod{8}\), so if \(d=4\) and the blackboard is left with \((1, 5)\), Bob wins.
Let us consider whether a perfect matching exists in the graph where, in addition to red edges, a blue edge is spun between vertices whose difference of the written numbers modulo \(M\) is \(M/2\) if \(M\) is even.

2.1 A state where \(G\) has no perfect matching (with any \(d\))

Here, \(u - v \neq v - u \pmod{M}\) holds for any pair of numbers \((u, v)\) written on vertices without an edge between them, so we see that Alice can win by an argument similar to the one in 1.3.

2.2 A state where \(G\) has a perfect matching (with any \(d\))

If there is a perfect matching, from 2.1, Bob must keep choosing a vertex connected by an edge to the vertex chosen by Alice, because otherwise there would be no perfect matching in the graph. (It is unnecessary to know the winner here, so we do not prove it.)

2.3 A state where \(G\) has a perfect matching at the beginning of the game

Consider the case there is a perfect matching formed by \(G\) at the beginning of the game. From 2.2, if both players play optimally, the vertices deleted by Alice and subsequently deleted by Bob in all \(2N\) operations must be connected by edges, so they form a perfect matching.
Here, we can verify that the parity of the number of blue edges is constant across all possible perfect matchings in \(G\). Choosing a red edge in a matching does not change \(d\) while choosing a blue edge shifts \(d\) by \(M/2\), so if there is an odd number of blue edges in an arbitrarily chosen perfect matching, Alice wins; otherwise, Bob wins.

All of the above show that the answer at the beginning is correct. One can use an associative array to compute it in about \(\mathrm{O}(N \log N)\) time, which is fast enough.

• Sample implementation (PyPy)

from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = defaultdict()
for a in A:
  D[a] ^= 1

blue = 0
while len(D):
  [key1, val1] = D.popitem()
  if val1 == 1:
    if M % 2 == 1:
      print("Alice")
      exit()
    key2 = (key1 + M // 2) % M
    val2 = D.pop(key2, 0)
    if val2 != 1:
      print("Alice")
      exit()
    blue += 1

print("Bob" if blue % 2 == 0 else "Alice")