前言：
谁知道我是怎么看教练的bug代码AC而怀疑人生的。已经研究困了。
思路：
博弈论最重要的是，发现模型并进行转模。这题很容易发现，与阶梯模型十分相似。可以考虑每个棋子距离 \(M\) 还有多少空格转化成当前在第几级阶梯。可是当我们转化后发现，胜利条件有一些不一样。阶梯模型是所有硬币到最后一级就算胜利，但在这里我们只需要有一枚硬币到最后一级就可以胜利。
起初我就是在这里卡住的。所以想到晚上睡觉的时候才想出来（不要晚上想题，会睡不着）。我们可以再往前推几步。以下推理均在对方操作时。
有一枚硬币到 \(M\) 格即为胜利，等价于有一枚硬币到 \(M-1\) 格即为失败，也就等价与所有硬币距离 \(M\) 只差两个空格时即为胜利。
请读者自己思考这段话，非常重要。
这样，我们就可以转模了。设每个棋子距离 \(M-2\) 还有多少空格为在第几级阶梯上即可。第零级的可以无视，因为博弈中两人只会在无法移动其他阶梯时才会移动（下一步对手就赢了）。转模后棋子有可能在负一级，这时需要特判，直接走就赢了。
但是阶梯求方案数并不是直接像nim游戏的石子堆一样。在判断是否能胜利时确实只有奇数阶有贡献，但算方案时，偶数阶也可能有贡献。偶数阶可能的贡献来源相当于在原有的石子堆中多加了一堆或者是增加其中一堆的石子，从而达到平衡态，而奇数阶的贡献来源则是拿掉其中一堆的部分或全部石子来达到平衡态。
理清思路后就可以开始coding了。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
TP void read(T &x)
{
x=0;int f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
x*=f;
}
TP_ void read(T &x,T_&...y){read(x);read(y...);}
TP void write(T x){if(x<0){putchar('-'),x=-x;}if(x>9)write(x/10);putchar(48+x%10);}
TP void writeln(const T x){write(x);puts("");}
TP void writesp(const T x){write(x);putchar(' ');}
TP_ void writeln(const T x,T_ ...y){writesp(x);writeln(y...);}
using LL=long long;
constexpr int N=1e6+5;
int n,m,a[N],c[N],f[N];
int main()
{
read(m,n);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=n;i++)//转模
a[i]=m-2-a[i]-n+i;
int len=0,ones=0;
for(int i=n;i>=1;i--)
{
if(a[i]==-1)
{
ones++;
continue;
}
else if(a[i])
{
if(f[len]!=a[i])
f[++len]=a[i],c[len]=1;
else
c[len]++;
}
}
if(ones){writeln(ones);return 0;}//1的特判
int res=0,ans=0;
for(int i=1;i<=len;i++)
if(f[i]&1)
res^=c[i];
if(!res){puts("0");return 0;}
for(int i=1;i<=len;i++)
{
if(f[i]&1)//减少其中一堆
{
if((res^c[i])>=0&&(res^c[i])<=c[i])
ans++;
}
else
if(f[i]-1!=f[i-1])//新加一堆
{
if(c[i]>=res)
ans++;
}
else//增加其中一堆
{
int s=(res^c[i-1])-c[i-1];
if(s>0&&s<=c[i])
ans++;
}
}
writeln(ans);
return 0;
}