[HNOI 2014]江南乐

Description

题库链接

给你指定一个数 (f) ，并给你 (T) 组游戏，每组有 (n) 堆石子， (A,B) 两人轮流对石子进行操作，每次你可以选择其中任意一堆数量不小于 (f) 的石子，平均分为 (m) 份（即保证最大的一堆和最小的一堆中石子数量之差不超过 (1) ）。不能操作者负。

问先手是否有必胜策略。

(T<100,N<100,F<100000,每堆石子数量<100000)

Solution

首先对于组合游戏，该游戏的 (sg) 函数是各个组分 (sg) 函数的 (nim) 和。

其次 (sg(x)=mex{sg(y)|y是x的后继状态}) 。由这两个性质我们可以来求初始状态为 (n) 态还是 (p) 态。

设法来求 (sg(x)) 。

我们可以枚举分的堆数 (i) 。

为了使数量尽量平均，我们应该使分出来每堆的石子数量尽可能等于 (lfloorfrac{x}{i} floor) ，如果每一堆分到(lfloorfrac{x}{i} floor) 个石子，那么最后会多出 (xmod i) 个石子。

考虑把这些多出来的石子分别放在分出来的石子堆中，那么有 (xmod i) 堆会分到新的石子。

经过简单的计算，我们可以发现最后有 (xmod i) 堆分到了 (lfloorfrac{x}{i} floor+1) 个石子，有 $ i-(xmod i)$ 堆分到了 (lfloorfrac{x}{i} floor) 。

由数论分块的思想，对于相同的块内，后继状态 (y) 最多只有两种，由于相同的数异或可以抵消，我们可以通过判断 (xmod i) 和 (i-(xmod i)) 的奇偶性来缩小运算规模。

Code

//It is made by Awson on 2018.3.7
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;

int sg[N+5], mex[N+5], t, F, n, x;

int f(int x) {
  if (sg[x] != -1) return sg[x];
  if (x < F) return sg[x] = 0;
  sg[x] = 0;
  for (int i = 2; i <= x; i = x/(x/i)+1) {
    int tmp = 0;
    if ((i-x%i)&1) tmp ^= f(x/i); if ((x%i)&1) tmp ^= f(x/i+1);
    mex[tmp] = x;
    if (i < x && (x/i == x/(i+1))) {
      ++i, tmp = 0;
      if ((i-x%i)&1) tmp ^= f(x/i); if ((x%i)&1) tmp ^= f(x/i+1);
      mex[tmp] = x;
    }
  }
  while (mex[sg[x]] == x) ++sg[x];
  return sg[x];
}
void work() {
  memset(sg, -1, sizeof(sg));
  scanf("%d%d", &t, &F); --t;
  while (t--) {
    scanf("%d", &n); int ans = 0; while (n--) scanf("%d", &x), ans ^= f(x); printf("%d ", (ans != 0));
  }
  scanf("%d", &n); int ans = 0; while (n--) scanf("%d", &x), ans ^= f(x); printf("%d
", (ans != 0));
}
int main() {
  work(); return 0;
}