Grundy数

No.715 集合と二人ゲーム | yukicoder

grundy数を出力して図にしてみる。 十分大きな整数について、そのgrundy数が34周期になっていることがわかる。 int dp[201]; int g(int n) { if (dp[n] != -1)RT dp[n]; set<int> S; for (int i = 0; i < n; ++i) { int l = max(0, i - 1); int r = max(n - 2 - i</int>…

F. Strange Nim | AtCoder Regular Contest 091

問題二人でニムっぽいゲーム山N個各山A[i]個の石山iから1<=a<=floor(X/K[i])個取れるA[i]=0, 1<=i<=N の状態で自分のターンになったら負け1<=N<=2001 <= A[i], K[i] <= 10^9 解説Grundy数がわかればいい。g(x, k) : x個の山, k個取れるときのGrundy数k>xのと…

Codeforces #399 E: Game of Stones

ニムのルールを少し変えたゲームの勝敗を知りたい。石の山の状態の数とその状態の遷移の数が十分小く表せれば、Grundy数やるだけ。山の状態を適切に表したい。愚直に考えれば山の状態=(石の個数, 1~60のうち取り除いたことのある個数についてのフラグ)たとえ…