#P3576. [Hnoi2014]江南乐

    ID: 2775 传统题 1000ms 512MiB 尝试: 2307 已通过: 623 难度: 7 上传者: 标签>难度分类提高+/省选-博弈论SG 函数异或合并位运算异或抵消mex 计算数论整除分块构造与建模奇偶性分析模拟与实现技巧时间戳避免清空数组CF2300

[Hnoi2014]江南乐

[HNOI2014] 江南乐

题目描述

小A是一个名副其实的狂热的回合制游戏玩家。在获得了许多回合制游戏的世界级奖项之后,小A有一天突然想起了他小时候在江南玩过的一个回合制游戏。

游戏系统给定阈值 FF,生成 TT 组游戏。每组有 NN 堆石子,双方轮流操作。每次选择一堆至少有 FF 颗石子的石子,将其拆成 MM 个非空堆,MM 是本次任选的整数,且 M≥2M\ge2。拆出的最多一堆和最少一堆相差至多一颗石子。

拆完后,新堆也留在桌面上供之后操作。例如,第一步拆出 MM 堆后,桌面上一共有 N+M−1N+M-1 堆。轮到某方而无法进行合法拆分时,该方输掉游戏。

小A从小就是个有风度的男生,他邀请他的对手作为先手。小A现在想要知道,面对给定的一组游戏,而且他的对手也和他一样聪明绝顶的话,究竟谁能够获得胜利?

输入格式

第一行两个正整数 T,FT,F,分别表示游戏组数和拆分阈值。接下来 TT 行,每行先给出初始堆数 NN,然后给出 NN 个正整数,分别表示各堆的石子数。

输出格式

输出一行 TT 个用空格分隔的整数。00 表示小 A(后手)获胜,11 表示对手(先手)获胜。

样例 #1

4 3
1 1
1 2
1 3
1 5
0 0 1 1

数据范围

原题给出 T<100T<100,N<100N<100,F<100000F<100000,每堆石子数小于 100000100000。以上各数均为正整数。