HNOI2014 江南乐

题目:

  小 A 是一个名副其实的狂热的回合制游戏玩家。在获得了许多回合制游戏的世界级奖项之后,小 A 有一天突然想起了他小时候在江南玩过的一个回合制游戏。
  游戏的规则是这样的,首先给定一个数 ,然后游戏系统会产生 组游戏。每一组游戏包含 堆石子,小 和他的对手轮流操作。每次操作时,操作者先选定一个不小于 的正整数 ( 是操作者自行选定的,而且每次操作时可不一样),然后将任意一堆数量不小于 的石子分成 堆,并且满足这 堆石子中石子数最多的一堆至多比石子数最少的一堆多 (即分的尽量平均,事实上按照这样的分石子方法,选定 和一堆石子后,它分出来的状态是固定的)。
  先手从 堆石子中选择一堆数量不小于 的石子分成 堆后,此时共有 堆石子,接下来后手从这 堆石子中选择一堆数量不小于 的石子,依此类推。当一个玩家不能操作的时候,也就是当每一堆石子的数量都严格小于 时,他就输掉。
  小A从小就是个有风度的男生,他邀请他的对手作为先手。小 A 现在想要知道,面对给定的一组游戏,而且他的对手也和他一样聪明绝顶的话,究竟谁能够获得胜利?

思路:

  题目中有一个没讲清楚的点:如果一堆石子大小为 ,这堆石子也不能操作。(不然 游戏就无法结束了)
  如果会 SG 函数的话, 的暴力应该还是比较简单的吧。枚举 ,根据 SG 函数的定义在后继状态中取 即可。求 SG 函数的代码实现如下:

int sg[1005];
bool mark[1005];
void getSG(int n, int f) {
    rep(i, max(2, f), n) {
        memset(mark, 0, sizeof mark);
        rep(j, 2, i) {
            int k = i / j, d = i % j;
            int tmp = 0;
            if(d % 2 == 1) tmp ^= sg[k + 1];
            if((j - d) % 2 == 1) tmp ^= sg[k];
            mark[tmp] = true;
        }
        while(mark[sg[i]]) sg[i]++;
    }
}

  注意到 的值只有 种,再加上两条 if 语句,不同的后继状态个数是 级别的。所以可以用数论分块的办法每次同时统计所有 相同的
  设当前统计的区间为 。对于任何一个区间中的 可以表示为 也就等于 。对于两个 if 语句是否成立也就是看这两个表达式的奇偶性,只要分类讨论 的奇偶性,看区间中元素的奇偶性是否满足即可。复杂度

代码:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;
const int N = 100005;

bool cur1;

template<class T>
inline void rd(T &a) {
#define gc getchar()
    char c;
    bool f = false;
    for(c = gc; !isdigit(c); c = gc) f |= (c == '-');
    for(a = 0; isdigit(c); c = gc) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
#undef gc
}

int sg[N];
bool mark[N];
int stk[N], top;
void getSG(int n, int f) {
#define add(x) do {if(!mark[x]) {mark[x] = true; stk[++top] = (x);}} while(0)
    rep(i, max(f, 2), n) {
        int las;
        for(int j = 2; j <= i; j = las + 1) {
            las = min(i, i / (i / j));
            int k = i / j;
            if((k & 1) == 1) {
                int tmp = ((i & 1) ? sg[k] : 0);
                if(las != j || (i & 1) != (j & 1)) 
                    add(tmp ^ sg[k + 1]);
                if(las != j || (i & 1) == (j & 1)) 
                    add(tmp);
            }
            else {
                int tmp = ((i & 1) ? sg[k + 1] : 0);
                if(las != j || (i & 1) != (j & 1))
                    add(tmp ^ sg[k]);
                if(las != j || (i & 1) == (j & 1))
                    add(tmp);
            }
        }
        while(mark[sg[i]]) sg[i]++;
        while(top) mark[stk[top--]] = false;
    }
    // rep(i, 1, 20) fprintf(stderr, "%d\n", sg[i]);
#undef add
}

bool cur2;

int main() {
    // printf("%lf\n", (&cur2 - &cur1) / 1024.0 / 1024);
    File(game);
    int f, t;
    rd(t); rd(f);
    getSG(1e5, f);
    rep(i, 1, t) {
        int tmp = 0, n;
        rd(n);
        rep(j, 1, n) {
            int a;
            rd(a);
            tmp ^= sg[a];
        }
        printf("%d%c", (tmp ? 1 : 0), " \n"[i == t]);
    }
    return 0;
}