记录编号	423791	评测结果	AAAAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2004]平板游戏	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.063 s
提交时间	2017-07-12 16:03:16	内存使用	4.12 MiB

#include<cstdio>
#include<map>
using namespace std;
const int N=1e6+10;
int m,n,a[N];
map<int,int> M;//M[i]表示距离终点有i个白格的棋子个数
typedef map<int,int>::iterator it;
int main()
{
	freopen("gra.in","r",stdin);
	freopen("gra.out","w",stdout);
	scanf("%d%d",&m,&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		M[m-a[i]-n+i-2]++;
	}
	if (M.count(-1)) return printf("%d\n",M[-1]),0;//可以直接取胜
	int xor_sum=0;
	for (it i=M.begin();i!=M.end();++i)
		if ((*i).first&1) xor_sum^=(*i).second;
	if (!xor_sum) return puts("0"),0;
	int ans=0;
	for (it i=M.begin();i!=M.end();++i)
	if ((*i).first>0){
		int p=(*i).first,v=(*i).second;
		if ((*i).first&1) ans+=((xor_sum^v)<v);
		else{
			int nxt=M.count(p-1)?M[p-1]:0;
			ans+=((xor_sum^nxt)<=nxt+v&&(xor_sum^nxt)>nxt);
		}
	}
	printf("%d\n",ans);
	return 0;
}