记录编号	103324	评测结果	AAAAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2004]平板游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.902 s
提交时间	2014-05-26 21:23:38	内存使用	4.13 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=1000010;
int N,M;//N个棋子,棋盘长M
int A[SIZEN]={0};
vector<pair<int,int> > pile;//first是阶梯nim中的堆编号,second是该堆的石子数
void work(void){
	if(A[N]==M-1){
		printf("%d\n",pile[0].second);
		return;
	}
	int sg=0,ans=0;
	for(int i=0;i<pile.size();i++) if(pile[i].first&1) sg^=pile[i].second;
	for(int i=0;i<pile.size();i++){
		if(pile[i].first==2) continue;
		for(int j=1;j<=pile[i].second;j++){//我们现在考虑把pile[i]相应第x堆的j个石子移向第x-1堆
			int now=sg;
			if(pile[i].first&1){//相应计算第x堆
				now^=pile[i].second;
				now^=pile[i].second-j;
			}
			int temp=0;
			if(i>0&&pile[i].first==pile[i-1].first+1) temp=pile[i-1].second;
			if(!(pile[i].first&1)){//相应计算第x-1堆
				now^=temp;
				now^=temp+j;
			}
			if(!now) ans++;
		}
	}
	printf("%d\n",ans);
}
void getpile(void){
	int nownum=0;
	A[N+1]=M+1;
	for(int i=N;i>=1;i--){
		if(A[i]==A[i+1]-1) pile.back().second++;
		else{
			nownum+=(A[i+1]-A[i]-1);
			pile.push_back(make_pair(nownum,1));
		}
	}
}
void read(void){
	scanf("%d%d",&M,&N);
	for(int i=1;i<=N;i++) scanf("%d",&A[i]);
}
int main(){
	freopen("gra.in","r",stdin);
	freopen("gra.out","w",stdout);
	read();
	getpile();
	work();
	return 0;
}