はじめに答えを書きます。

頂点 \(i\) に \(A_i\) を書きこんだ \(2N\) 頂点のグラフを考えます。同じ数が書きこまれた頂点の間に赤い辺を貼ります。また、\(M\) が偶数の場合、(書きこまれた数の差 \(\text{mod }M\)) が \(M/2\) である頂点の間に青い辺を貼ります。
このとき、青い辺を偶数本使うような完全マッチングが存在すれば Bob の勝ち、そうでない場合は Alice の勝ちです。

正当性を確認していきます。 以下の議論では、常に Alice 側が手番である状態のみを評価する ことに注意してください。
はじめに、ゲームの状態を表現する言葉を定義します。 今、黒板に \(B = (B_1, B_2, \dots, B_{2k})\) が残っていて、Alice が消した数の和を \(S\) 、Bob が消した数の和を \(T\) とします。\(B_1, B_2, \dots, B_{2k}\) に関して上記の説明の通りに構成したグラフを \(G\) と呼びます。また、\((S-T) \bmod M\) を \(d\) とします。

1. \(M\) が奇数の場合

\(M\) が奇数である場合は簡単なので、理解を兼ねてまずこれを説明します。
\(M\) が奇数の場合は \(G\) に赤い辺のみが貼られているので青い辺の条件は無視できます。いくつか場合分けして考えます。

1.1 \(G\) に完全マッチングが存在して、かつ \(d=0\) の状態

この場合は Bob がいわゆる「真似っこ戦略」を取れば勝つことができます。すなわち、常に Alice が消した数と同じ数を消していけばよいです。
正当性については、\(G\) が空の場合は Bob の勝ちで、\(|G| \gt 0\) の場合は常に頂点サイズが \(2\) 小さい場合に帰着できることから帰納的に示せます。

1.2 \(G\) に完全マッチングが存在して、かつ \(d \neq 0\) の状態

\(\vert G \vert = 0\) の場合明らかに Alice の勝ちです。 \(\vert G \vert \gt 0\) の場合は Alice が(少し変則的な)真似っこ戦略を取れば勝つことができます。すなわち、次のような戦略です。

1. Alice は \(B\) の元 \(x\) を 1 つ任意に選び、消す。
2. 次に Bob が \(y \neq x\) である \(y\) を消した場合は Alice も \(y\) を消す。これを Bob が \(x\) を消すまで繰り返す。
3. 2.を \(0\) 回以上繰り返した後に Bob が \(x\) を取ったとする。このときのグラフ \(G'\) は完全マッチングが存在し、かつ \(d\) は \(0\) のままなので、Alice は 1.に戻って同様の手順を繰り返すことができる。

上記の戦略を繰り返すことで、Alice は \(d \neq 0\) を保ったまま \(\vert G \vert = 0\) にすることができます。

1.3 \(G\) に完全マッチングが存在しない状態 (\(d\) は任意)

黒板に \(B=(B_1, B_2, \dots, B_{2k})\) が残っているとします。
はじめに \(G\) の最大マッチングのサイズが \(k-1\) である場合を考えます。このときマッチングに使用されない頂点に書かれている数を \(u, v\) とします。
このとき \(u \neq v\) かつ \(M \bmod 2 = 1\) なので、\((u - v) \bmod M\) と \((v - u) \bmod M\) は互いに異なります。(\(\because u-v\equiv v-u \iff 2(u-v) \equiv 0 \pmod{M}\) ) よって、\((d + u - v) \bmod{M}\) と \((d - u + v) \bmod{M}\) の少なくとも一方は \(0\) ではありません。ここで \((d + u - v) \bmod{M} \neq 0\) として一般性を失いません。
このとき、Alice は \(u\) を黒板から消して、以下 1.2 と同様の真似っこ戦略を取れば良いことが確認できます。(詳細は省略します)
\(G\) の最大マッチングのサイズが \(k-2\) 以下の場合は、マッチングを構成しない頂点に書かれた数を常に消していれば、のちに \(\vert \text{(最大マッチングのサイズ)}\vert + 1 = \vert G \vert / 2\) である場合に合流します。

2. \(M\) が一般の場合

\(M\) が一般、特に偶数の場合は 1.3 の証明は成り立ちません。たとえば \(M = 8\) で \((u, v) = (1, 5)\) の場合、\(1 - 5 \equiv 5 - 1 \equiv 4 \pmod{8}\) なので、例えば \(M=8,d=4\) で \((1, 5)\) のみを黒板に残した場合は Bob の勝ちです。
赤い辺に加えて、\(M\) が偶数の場合に (書きこまれた数の差 \(\text{mod }M\)) が \(M/2\) である頂点の間に青い辺が貼られたグラフについて、完全マッチングが存在するかどうかを考えます。

2.1 \(G\) に完全マッチングが存在しない状態 (\(d\) は任意)

この場合は、辺が張られていない頂点に書かれている数の組 \((u, v)\) について \(u - v \neq v - u \pmod{M}\) が成り立つので、1.3 と同様の議論により Alice が勝てることを確認できます。

2.2 \(G\) に完全マッチングが存在する状態 (\(d\) は任意)

完全マッチングが存在する場合、2.1 より Bob はそれ以降常に Alice が選んだ頂点と辺で結ばれた頂点を選び続ける必要があります。なぜならば、そのような頂点を選ばなかった時点で、グラフ上に完全マッチングが存在しなくなるからです。(勝敗はここでは必要ないので証明しません)

2.3 ゲーム開始時点での \(G\) に完全マッチングが存在する状態

ゲーム開始時点での \(G\) が完全マッチングをなす場合を考えます。2.2 より、双方が最適に動いたときに \(2N\) 回の操作全体で Alice が消した頂点とその直後に Bob が消した頂点は辺で結ばれている必要があります。よって、それらは完全マッチングをなします。
ここで、\(G\) の完全マッチングとして有り得る全てのマッチングについて、マッチングが含む青い辺の偶奇は常にどちらか一方で固定されているのが確認できます。マッチングの赤い辺を選んでも \(d\) は変わらず、青い辺を選ぶごとに \(d\) は \(M/2\) ずれるので、適当な完全マッチングを 1 つ選んだ時のマッチングに含まれる青い辺が奇数本ならば Alice の勝ち、偶数本ならば Bob の勝ちです。

以上より、最初に書いた答えが正しいことが証明できました。実装は連想配列を用いれば \(\mathrm{O}(N \log N)\) 程度で計算できて、これは十分高速です。

• 実装例(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")