TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

66.7% (10/15)

Submission's AC Ratio

26.7% (36/135)

Description

  小蘋與阿谷在玩撿豆豆遊戲,盤面上有一群豆豆,小蘋與阿谷輪流從中拿出若干豆豆,每次可拿走的顆數是有限制的,直到一方無法再拿走豆豆的人輸,經過猜拳決定,這個遊戲將由小蘋先執行。
  比如說盤面上有五顆豆豆,每次每人一定要拿走 2 顆或 3 顆,此時如果小蘋拿走 2 顆,則阿谷必定拿走 3 顆,則小蘋因無法再執行任何動作而輸。如果小蘋拿走 3 顆,則阿谷必定拿走 2 顆,則小蘋也是輸。所以小蘋必輸無疑。又比如說盤面上有 5 顆豆豆,每次每人一定要拿走 3 顆或 4 顆,此時如果小蘋拿走 3 顆,盤面上只剩 2 顆,則阿谷無法再執行任何動作而輸。如果小蘋拿走 4 顆,盤面上只剩 1 顆,則阿谷也是輸。所以小蘋必贏無疑。
  聰明的小蘋發現,當一個遊戲中沒有隨機成分,且總會終止時,其中一方必定有必勝策略。於是她想要趁遊戲開始之前偷偷吃掉$x$顆豆子($x$不得超過盤面上的豆子總數),使得由小蘋先執行的時候永遠立於不敗之地。假設小蘋與阿谷都是絕頂聰明,請問她有幾種選擇非負整數$x$的方法呢?

Input Format

第一行有一個正整數$m$,表示盤面上有$m$顆豆豆。第二行有一個正整數$n$,後面接著$n$個以空白隔開的正整數$a_1, a_2, \cdots, a_n$,代表每次可以拿走的豆豆顆數。

子任務(測資) 額外限制 分數
1 (0~4) $m\leq 1000, n\leq 2, a_i\leq 10$ 20
2 (0~9) $m\leq 10^ 5,n\leq 5, a_i\leq 10^ 5$ 35
3 (0~14) $ m\leq 10^ 8, n\leq 10, a_i\leq 10^ 8$ 12
4 (15~22) $ m\leq 10^ {18}, n\leq 20, a_i\leq 20$ 33

Output Format

請輸出有幾種方式選擇非負整數$x$,使得小蘋可以獲得勝利。

Sample Input

#Sample Input 1
5
2 2 3
#Sample Input 2
6
2 1 6
#Sample Input 3
948794
7 9 48 79 487 879 4879 8794
#Sample Input 4
1000000000000000000
5 3 9 11 13 18

Sample Output

#Sample Output 1
3
#Sample Output 2
4
#Sample Output 3
565273
#Sample Output 4
761904761904761904

Hints

怪異的時限是模擬模考時的情況。

Problem Source

題目取自2017 TOI選訓第二次模擬考pA
Problem set by Yihda Yol

Subtasks

No. Testdata Range Score
1 0~4 20
2 0~9 35
3 0~14 12
4 15~22 33

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 916 262144 262144 1 2 3
1 916 262144 262144 1 2 3
2 916 262144 262144 1 2 3
3 916 262144 262144 1 2 3
4 916 262144 262144 1 2 3
5 916 262144 262144 2 3
6 916 262144 262144 2 3
7 916 262144 262144 2 3
8 916 262144 262144 2 3
9 916 262144 262144 2 3
10 916 262144 262144 3
11 916 262144 262144 3
12 916 262144 262144 3
13 916 262144 262144 3
14 916 262144 262144 3
15 916 262144 262144 4
16 916 262144 262144 4
17 916 262144 262144 4
18 916 262144 262144 4
19 916 262144 262144 4
20 916 262144 262144 4
21 916 262144 262144 4
22 916 262144 262144 4