OI题库

【题目描述】

让我们考虑一个在1行m列矩形网格上的游戏。这张网格共有m格，从左到右被命名为1到m。网格上有n个棋子，每个都独占一格。没有棋子占据m号格。每回合如下：该回合进行移动的玩家任意选择一枚棋子，并且把它放到第一个编号更大的空格子中。两名玩家轮流进行移动。把棋子放在最后一格，也就是m号格子的玩家胜利。

下图给出了一个例子（m=7），现在玩家可以把棋子从2移动到4，从3移动到4或者从6移动到7.

我们说玩家的一个移动可以获胜，如果在此之后无论对手如何移动，他都能获胜。

写一个程序来完成以下任务：

·读入棋盘的规模和最初棋子的位置。

·计算在这种情况下先手可以获胜的不同移动方案数。

·输出结果。

【输入格式】

输入文件的第一行有两个空格隔开的整数m,n（2<=m<=10^9，1<=n<=10^6，n<m）。

第二行有n个递增整数，即最开始棋子的位置。这些整数由空格隔开。

【输出格式】

输出一行一个整数，即对于所给开局，先手可以获胜的不同移动方案数。

【样例输入】

输入样例1：

5 2

1 3

输入样例2：

5 2

2 3

【样例输出】

输出样例1：

1

输出样例2：

0

【来源】

POI 2003/2004 I stage Game