小蘋與阿谷在玩撿豆豆遊戲,盤面上有一群豆豆,小蘋與阿谷輪流從中拿出若干豆豆,每次可拿走的顆數是有限制的,直到一方無法再拿走豆豆的人輸,經過猜拳決定,這個遊戲將由小蘋先執行。
比如說盤面上有五顆豆豆,每次每人一定要拿走 2 顆或 3 顆,此時如果小蘋拿走 2 顆,則阿谷必定拿走 3 顆,則小蘋因無法再執行任何動作而輸。如果小蘋拿走 3 顆,則阿谷必定拿走 2 顆,則小蘋也是輸。所以小蘋必輸無疑。又比如說盤面上有 5 顆豆豆,每次每人一定要拿走 3 顆或 4 顆,此時如果小蘋拿走 3 顆,盤面上只剩 2 顆,則阿谷無法再執行任何動作而輸。如果小蘋拿走 4 顆,盤面上只剩 1 顆,則阿谷也是輸。所以小蘋必贏無疑。
聰明的小蘋發現,當一個遊戲中沒有隨機成分,且總會終止時,其中一方必定有必勝策略。於是她想要趁遊戲開始之前偷偷吃掉$x$顆豆子($x$不得超過盤面上的豆子總數),使得由小蘋先執行的時候永遠立於不敗之地。假設小蘋與阿谷都是絕頂聰明,請問她有幾種選擇非負整數$x$的方法呢?
第一行有一個正整數$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 |
請輸出有幾種方式選擇非負整數$x$,使得小蘋可以獲得勝利。
怪異的時限是模擬模考時的情況。
題目取自2017 TOI選訓第二次模擬考pA
Problem set by Yihda Yol
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 20 |
2 | 0~9 | 35 |
3 | 0~14 | 12 |
4 | 15~22 | 33 |