一个标准的NIM游戏 加上一条规则:每堆石子对于每个数目的石子只能被取一次
可以SG打表
dp[i][j]表示现在有i个石子 j是可以取的石子数的状压 第i位为1就表示i个石子没被取过
#include <cstdio>
#include <cstring>bool vis[];int mex() {
for(int i = ; ; i++) if(!vis[i]) return i;
}int sg[][ << ];int main()
{
memset(sg, -, sizeof(sg));
for(int i = ; i < ( << ); i++) sg[][i] = ;
for(int i = ; i <= ; i++) {
sg[i][] = ;
for(int j = ; j < ( << ); j++) {
memset(vis, false, sizeof(vis));
for(int k = ; k < i; k++) if((j >> k) & )
vis[sg[i - k - ][j ^ ( << k)]] = true;
sg[i][j] = mex();
}
} for(int i = ; i <= ; i++)
printf("i = %d: sg = %d\n", i, sg[i][( << i) - ]); return ;
}
打表找到规律数X的SG值就是该数最多能被多少个整数划分 即找到最大的Y 使得sum(1~Y)<=X Y即为数X的SG值
#include<iostream>
#include<cstdio>
using namespace std;
int n,ans;
int main()
{
int i,j,p;
cin>>n;
for(i=;i<=n;i++)
{
scanf("%d",&p);
for(j=;j*(j+)/<=p;j++);
ans^=j-;
}
ans?puts("NO"):puts("YES");
}