Problem

Input

Output

Hint

Solution

刚看到题就知道是正解想不出暴力打不出的博弈。。。
比赛时我也想了一会，但是只想到了40points。。。

40points：状压DP or 记忆化搜索

40points的m≤20，可以考虑二进制压缩状态。
对于每一位，为0表示无棋子，为1表示有棋子。
这样的话，状态数是$O(2^m)$级别的。对于每个状态的每一位，可以处理出它会往后跳到哪一格。
设tot[i]表示状态i的必胜走法。显然，如果i的第m位为1，则肯定是必胜的。此时，$i≥2^{m-1}$。
考虑逆着DP。也就是说，对于某个必败态，将其中的某个棋子往左移动，转化为某个必胜态，使其必胜走法++。可以发现，如果我们正着跳，肯定会使状态i增大；那么我们要逆着DP，则可以逆序枚举状态i来转移。
时间复杂度：$O(2^mm)$。

Code

#include <cstdio>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;

const int M=21,S=(1<<M)-1;
int i,j,k,m,n,s,fir,a,st;
ll tot[S];

int calc(int s)//计算状态s中有多少个棋子
{
    return s?(s&1)+calc(s>>1):0;
}
inline int pos(int x){return 1<<x-1;}//返回x的状态
inline bool in(int x){return pos(x)&i;}//判断位于x的棋子是否在状态i中
int main()
{
    scanf("%d%d",&m,&n);s=(1<<m)-1;
    fo(i,1,n)scanf("%d",&a),st+=pos(a);//st记录起始状态
    fd(i,s-1,st+1)
        if(!tot[i]&&calc(i)==n)
        {
            fir=0;
            fo(j,1,m)
            {
                if(!in(j)){fir=j;continue;}
                if((!in(m)||j==m)&&fir)
                {
                    k=i-pos(j)+pos(fir);
                    tot[k]++;
                }
            }
        }
    printf("%lld",tot[st]);
}

100points：阶梯nim

其实这题可以转化成阶梯nim。
首先，我们需要特判a[n]=m-1的情况。此时，答案为末尾连续的棋子个数。因为末尾的那堆棋子都可以一步移到m。
那么，a[n] < m-1怎么办？
譬如有如下的一块板子：

如果此时所有的棋子都聚集在m-2（所有棋子连续，最后一个棋子在m-2），那么这是一个必败态。所以可以把第m-2个位置设为第0层。
然后，我们将连续的棋子放在同一层；若碰到空格，则忽略其中一个，然后令其他的空格独踞一层。
也就是说，我们每碰到一个棋子，就加进当前层；每碰到一个空格，就令层数++。于是，两个相邻（a[i]与a[i+1]）棋子的层数差即为它们间的空格数。
所以说，上图中的第0层有2个棋子（即a[5]、a[6]）；第3层有3个棋子（即a[2]、a[3]、a[4]）；第4层有1个棋子（即a[1]）。如果我们将a[1]后移一格，它就会与a[2]、a[3]、a[4]连在一起；所以对应它往下跳一层，就可以与a[2]、a[3]、a[4]处在同一层。
于是，这就转化成了一个阶梯nim游戏。SG=奇数层棋子数的异或和。
当SG=0时必败，SG=1时必胜。但这题并不让我们判断是否必胜，而是要我们求必胜走法方案数。
我们可以分类讨论：从奇数层移到偶数层，设那个奇数层有a个棋子，此时相当于取走若干个棋子，那么只要它满足a>SG^a，我们就可以取走若干个，使它剩下SG^a个，然后SG值就会变成0，所以此时ans++；从偶数层移到奇数层，设偶数层有c个棋子，奇数层有d个棋子，只要它满足c+d≥SG^d且d < SG^d，我们就可以从c移若干个给d，把d补至SG^d个，SG值就会变成0，所以此时也让ans++。
当然，这可能有$O(m)$层，我们只需记录有棋子的层的信息即可。
时间复杂度：$O(n)$。

Code

#include <cstdio>
#include <cctype>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;

const int N=1e6+9;
int i,j,m,n,a[N],t,b[N],c[N],d[N],SG,tot;

void read(int&x)
{
    char ch=getchar();x=0;
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
}
int main()
{
    read(m);read(n);
    fo(i,1,n)read(a[i]);

    if(a[n]==m-1)
    {
        fd(i,n-1,1)if(a[i]+1<a[i+1])break;
        printf("%d",n-i);
        return 0;
    }

    a[0]=-1;a[n+1]=m-1;
    for(i=n;i;i=j-1)
    {
        t+=a[i+1]-a[i]-1;
        fd(j,i,1)if(a[j-1]+1<a[j])break;
        if(t&1) b[++b[0]]=i-j+1;
        else
        if(t)
        {
            c[++c[0]]=i-j+1;
            if(a[i]+2==a[i+1])d[c[0]]=b[b[0]];
        }
    }

    fo(i,1,b[0])SG^=b[i];
    if(!SG){putchar('0');return 0;}
    fo(i,1,b[0])tot+=(b[i]>=(b[i]^SG));
    fo(i,1,c[0])tot+=(c[i]+d[i]>=(d[i]^SG)&&d[i]<(d[i]^SG));
    printf("%d",tot);
}