[POI 2004] Gra

Luogu
IDLGP8382
Time1000ms
Memory128MB
DifficultyP6
2004POI(波兰)
让我们考虑一个在 $m \times 1$ 的板子上玩的游戏,板子被从 $1$ 到 $m$ 编号。 现在板子上有 $n$ 个棋子,每个都严格占据板子上的一个格子,没有一个棋子占据格子 $m$。 每个单独的移动遵循以下原则:移动的人选择一个棋子把它移动到比它大的格子中第一个未被占据的格子里去。两个选手交替移动,谁先占据格子 $m$ 谁赢。 我们在当且仅当他移动以后令一选手无论如何都无法赢他的时候说当前选手的移动称作 $\text{winning}$ 操作。 我们想知道先手有多少个移动是 $\text{winning}$ 操作。 ## Input 第一行有两个数 $m,n$ 。 然后接下来 $n$ 个上升的整数表示初始被占据的格子编号。 ## Output 输出先手有多少移动是 $\text{winning}$ 操作。 [samples] ## Note 对于 $100$ % 的数据:$2 \le m \le 10^{9}, 1 \le n \le 10^{6}$ ,且有 $n + 1 \le m$ 。 下面是一个例子: ![](https://cdn.luogu.com.cn/upload/image_hosting/obrkvr84.png) 在 $m = 7$ 的时候,一个选手可以把 $2$ 移到 $4$,把 $3$ 移到 $4$ 或者把 $6$ 移动到 $7$。
Samples
Input #1
5 2
1 3
Output #1
1
API Response (JSON)
{
  "problem": {
    "name": "[POI 2004] Gra",
    "description": {
      "content": "让我们考虑一个在 $m \\times 1$ 的板子上玩的游戏,板子被从 $1$ 到 $m$ 编号。  现在板子上有 $n$ 个棋子,每个都严格占据板子上的一个格子,没有一个棋子占据格子 $m$。  每个单独的移动遵循以下原则:移动的人选择一个棋子把它移动到比它大的格子中第一个未被占据的格子里去。两个选手交替移动,谁先占据格子 $m$ 谁赢。 我们在当且仅当他移动以后令一选手无论如何都无法赢他",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8382"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "让我们考虑一个在 $m \\times 1$ 的板子上玩的游戏,板子被从 $1$ 到 $m$ 编号。 \n\n现在板子上有 $n$ 个棋子,每个都严格占据板子上的一个格子,没有一个棋子占据格子 $m$。 \n\n每个单独的移动遵循以下原则:移动的人选择一个棋子把它移动到比它大的格子中第一个未被占据的格子里去。两个选手交替移动,谁先占据格子 $m$ 谁赢。\n\n我们在当且仅当他移动以后令一选手无论如何都无法赢他...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments