Yukicoder008 N言っちゃダメゲーム

問題概要

2人で次のゲームを行う。 $N,K$が与えられる。 プレイヤーは$0$から数字を$[1,K]$だけ加算し、相手にその数を渡す。 $N$を言った方の負け。 両者が最適に行動したときどちらが勝つか。

$test\leqq10^2$、$2≦N\leqq1.2*10^5$、$2≦K≦1.2*10^5$

yukicoder008

解法

周期性に着目する。

解法やgrundy数についての詳細はここに書いたので割愛します。

競プロにおけるNim、Grundy数とNimK

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        FOR(i, 0, N) {
            int n, k; cin >> n >> k;
            ans = (n - 1) % (k + 1);
            cout << (ans == 0 ? "Lose" : "Win") << endl;
        }
    
        return 0;
    }