ARC148 D - mod M Game (700)
同じ数字が二つある場合はアリスが消した後にボブが消すことで剰余を変えないようにボブができる
なのでペアになっている数字は除外
ペアでない数字がない場合は上の流れでボブの勝ち
$ mが奇数の場合はアリスの勝ち
最後2個の時に剰余が等しくならない方を選ぶことで勝てる
偶数の場合、$ m=10,a=\{1,6\}の様な場合にどちらを選んでも剰余の差が変わらない場合がある
残った数字を$ \frac{m}{2}でソートしておく
$ \frac{m}{2}の剰余でペアの数字の数をカウントしておく
カウントが偶数でカウントがちょうど$ nの半分だったらボブの勝ち
つまり全てがペアになる
カウントが奇数だと同じ数字ではないが$ \frac{m}{2}の剰余が同じペアが奇数ということなので最終的に$ mでの剰余が$ \frac{m}{2}ずれることになる
それ以外ならアリスの勝ち