H. Split Game
1.0 s
256 MB
standard input
standard output
For a long time, rich clientele of Binary Casino has been requesting a new way to gamble their money. To fulfill their wishes, the director of Binary Casino decided to introduce a new game called Split Your Tokens.
This game is played only when a customer is about to exit the casino. Instead of exchanging tokens won during his visit, he may take up casino's challenge and bet all of his earned tokens on winning this game. Should the customer lose, all of his tokens are lost in favor of the casino.
When the game starts, the customer splits his tokens into NN piles with not necessarily same amount of tokens in each pile. The customer and the casino then exchange turns in this game we denote the customer as the first player and the casino as the second player. Each player in his turn decides which pile he wants to split and chooses a positive integer KK which is smaller than the size of the selected pile. Then the player splits the selected pile into as many piles of size KK as possible. If any tokens remain, they form another pile on their own. A player loses the game when he can not do any more splitting. The customer (first player) always plays first.
The director of Binary Casino is however not sure, whether this game will be profitable for the casino in the long term. Your task is thus to determine, for a given configuration of piles, which player wins when both players play optimally.
The first line contains one integer NN (1≤N≤20001≤N≤2000), the number of piles. The second line contains a sequence of NN integers PiPi (1≤Pi≤20001≤Pi≤2000), PiPi represents the number of tokens in the ii-th pile.
Output a single line with either "First" or "Second", depending on which player wins the game if both play optimally.
3
1 2 3
First
3
1 2 2
Second
题意概括：
给出 N 堆物品， 两个玩家轮流选择将其中一个大小为 M 的堆 分成最多的 大小为 K （K < 当前选择的堆的大小）的堆，若 M%K 有剩余，则剩余的自成一堆。
最后所有堆大小都为 1 时不可再分，不能再分堆的玩家输。
解题思路：
因为SG函数的作用就是把博弈的状态当成一个点，然后形成一张 有向图，后继状态也就是后继结点，通过转移图上结点的状态最后求的起始点的结果。
以往 都是选择某一堆 取走若干 然后留下一堆，所以 结点的后继结点就对应剩下的那个状态。也就是说 把每一堆单独作为一个 NIM游戏，最后再考虑所有堆最后异或的结果。
不过 这里是选择某一堆 然后分成若干个小堆，就相当于又变成了一个 NIM游戏，不过考虑到分成的若干小堆 有相同的 和 不同的两部分，相同的直接判奇偶即可，如果有不同的（即分剩下的）再异或上这种状态即可。也就是先把每一堆作为一个 NIM 游戏，每分一次就又玩一次 NIM 游戏。
AC code：
#include <bits/stdc++.h>
#define inc(i, j, k) for(int i = j; i <= k; i++)
#define rep(i, j, k) for(int i = j; i < k; i++)
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
#define INF 0x3f3f3f3f
#define LL long long
#define MEM(i, j) memset(i, j, sizeof(i));
#define gcd(i, j) __gcd(i, j)
using namespace std;
const int MAXN = 2e5+;
const int MM = 2e3+;
int sg[MAXN];
int vis[MAXN]; void getsg()
{
int cnt, res;
sg[] = ;
MEM(vis, -);
inc(i, , MM){
rep(j, , i){
cnt = i/j;
res = i%j;
if(cnt%) vis[sg[res]^sg[j]] = i;
else vis[sg[res]] = i;
}
int k = ;
while(vis[k] == i && k < MM) k++;
sg[i] = k;
}
} int main()
{
getsg();
int N;
scanf("%d", &N);
int ans = , tp;
while(N--){
scanf("%d", &tp);
ans^=sg[tp];
}
if(ans) puts("First");
else puts("Second");
return ;
}