TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

85.7% (6/7)

Tags

Description

卑鄙原之助跟朋友在玩 nim,盤面已經決定好了,總共有 $n$ 堆,第 $i$ 堆有 $a_i$ 個石子。

因為卑鄙源之助很卑鄙,他會偷藏薯條,也會偷藏石子,他可以遊戲開始前選其中幾堆藏起來。

因為卑鄙源之助很卑鄙,比賽過程中他也會作弊,他在比賽過程中,當輪到他時,他可以選擇做正常的 nim 操作,或是也可以選擇做卑鄙操作,以下是卑鄙操作的定義。

  • 把場上其中一堆石子丟掉(那堆石子就不見了),然後把自己當初藏起來的一堆石子加入場上(加入的那些石子自成一堆,而且只能選擇當初藏起來的其中一堆石子,不能把多堆合起來或是只放一堆的其中一部份)。

如果卑鄙源之助做完操作之後,場面看起來完全沒有變化,對手會發現在作弊,因此如果進行卑鄙操作,丟掉的堆跟換上去的堆不能一樣大。

卑鄙源之助是後手,請問卑鄙源之助開始時有幾種藏石子的方法(幾種石子堆的子集合),可以使他獲勝。

註:

  1. 不藏或是全部都藏都是合法的
  2. 藏起不同編號的石子堆即算不同種藏法

Input Format

輸入第一行有一個正整數 $n$,表示堆數。

第二行有 $n$ 個數字 $a_1,a_2,\ldots a_n$,$a_i$ 表示第 $i$ 堆的石子數。

  • $1 \leq n \leq 26$
  • $1 \leq a_i \leq 10^ 9$

Output Format

輸出一個數字,表示有幾種藏石子的方法,使卑鄙源之助獲勝。

Sample Input 1

1
18

Sample Output 1

1

Sample Input 2

3
2 2 2

Sample Output 2

4

Hints

Problem Source

IOICamp 2021 Day5 pE

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~40 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2
33 1000 262144 65536 2
34 1000 262144 65536 2
35 1000 262144 65536 2
36 1000 262144 65536 2
37 1000 262144 65536 2
38 1000 262144 65536 2
39 1000 262144 65536 2
40 1000 262144 65536 2