Educational DP Contest / DP まとめコンテスト K - Stones
解法
素直にグランディ数を求めれば良いです。例によってグランディ数についてはこちらがわかりやすいかと思います。
今回は、重要なのがグランディ数は0であるか1であるか、なので2以上の場合も1にしてしまいます。
個石が存在する場合のグランディ数
とすると、の場合は後手の勝利、ならば先手の勝利です。
初期状態はになります。
は、次のようにして求めることができます。
以下のについて、がすべてであれば、そうでなければ
これは定義にのっとった計算方法です。これをもとにして素直に遷移していけば、が計算できます。