まず、この問題は「 Alice が手持ちのカードの最後の 1 枚を出す瞬間」に注目することが重要です。理由は以下の通りです。

• 2 枚以上手札を持っている人は、出したら負けのカードがあってもそれを出さない選択ができるため、すぐに負けになることはない
• Alice が最後の 1 枚を出して負けにならなかったら、Bob が最後の 1 枚を出した後の結果に関わらず Alice の勝利となる
• \(\to\)「Alice が手持ちのカードの最後の 1 枚を出して負けになるかどうか」が勝敗を分けることになる

Bob の手札の最後の 1 枚を \(b\) とします。この時、Alice が最後の 1 枚を出した時の場に出たカードの数の総和は \(N(N+1) - b\) になります。よって、\(N(N + 1) - b\) が \(0\) になり得るかどうかで場合分けをします。

(1) \(N(N + 1) - b\) が \(0\) になり得る、すなわち \(1 \leq (N(N+1) \bmod M) \leq N\) である場合

\(c = N(N + 1) \bmod M\) とします。Bob はそれ以前の \(N-1\) 回の行動で \(c\) 以外のカードを出し切って \(b = c\) とすることが出来れば、Alice は最後の 1 枚を出した瞬間に負けになるため Bob の勝ちです。そして、実はそれは常に可能です。具体的には、次のように行動すればよいです。

• Bob の手札が 3 枚以上の時：\(c\) 以外に \(2\) 枚以上のカードを持っているので \(c\) を出さなくても負けることは無い。
• Bob の手札が 2 枚の時：Alice が持っている最後の 1 枚のカードを \(a\) とした時、Bob が最後から \(2\) 枚目のカードを出した時の場のカードの数の総和は \(N(N+1) - c - a = M-a \pmod{M}\) でこれは非 \(0\) である。よって Bob は負けにならない。

(2) \(N(N + 1) - b\) が \(0\) になり得ない場合

この場合 Bob がどのように行動しても Alice は最後の 1 枚を出した瞬間に負けになることはありません。よってこの場合は Alice が勝ちます。

以上より、「\(N(N + 1) \bmod M\) が \(1\) 以上 \(N\) 以下であれば Bob の勝ち、そうでなければ Alice の勝ち」がこの問題の答えとなります。これは \(\mathrm{O}(1)\) で判定できます。