#P3618. [Zjoi2014]取石子游戏

    ID: 1774 传统题 2000ms 256MiB 尝试: 52 已通过: 9 难度: 10 上传者: 标签>难度分类省选/NOI-博弈论SG 函数异或合并mex 计算位运算异或抵消模拟与实现技巧进位制转换高精度除法Brian Kernighan 算法CF2900

[Zjoi2014]取石子游戏

[ZJOI2014] 取石子游戏

题目描述

Roland P. Sprague 和 Patrick M. Grundy 都喜欢组合游戏,却素未谋面。

Sprague 写信给 Grundy,向他介绍据说来自东方的取石子游戏。一开始桌上有若干堆石子。两人轮流选取一堆,取走其中至少一颗石子。轮到某人时如果无法操作,他就输掉游戏。两人没有合适的场地,便在纸上写下一排自然数来表示各堆的石子数,轮流划掉旧数和写下新数。

Grundy 连输五局后,发现可以由初始数列判断谁有必胜策略,并求出这种策略。第二天,他写信建议改变规则。先指定一个常数 KK,每次操作时选择纸上的一个数 xx,再选择一个正整数 aa,满足 x−Ka≥0x-Ka\ge0。划掉 xx,写下以下 KK 个数。

x−a, x−2a, …, x−Kax-a,\ x-2a,\ \ldots,\ x-Ka

如果对某个 xx 找不到合法的 aa,本回合就不能划掉这个数。轮到某人时没有合法操作,此人输掉游戏。

Sprague 接受了新规则。现在他把 KK 和纸上的 NN 个初始数告诉了你。你扮演正在研究如何用计算机解决实际问题的 John von Neumann。求两人都采用最优策略时的结果。

输入格式

第一行一个正整数 TT,表示数据组数。每组数据前有一空行。随后一行两个正整数 N,KN,K,接下来 NN 行每行一个正整数,依次表示纸上的初始数。

输出格式

每组数据输出一行。先手有必胜策略时输出 Preempt.,后手有必胜策略时输出 Leapfrog.,两者都没有必胜策略时输出 Je suis un imbecile.。

样例

2

1 1
1

2 30
197943
249832
Preempt.
Leapfrog.

数据规模与约定

1≤T≤101\le T\le10。

题源所列数据比例 NN 的上限 KK 每个初始数的上限
10%10\% 55 11 55
20%20\% 100100 10910^9
10%10\% 22
20%20\% 101810^{18}
1010
40%40\% 3030 108010^{80}