TopCoder

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

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

73.3% (22/30)

Tags

Description

《理春議》是一篇描寫十六進位制的古文,堪稱是中國數學史上第一個提到十六進位制的文章,具有極高的數學價值。
為了切合題意,以下題目敘述所提到的所有數字一律採用十六進位表示法(最下方「Subtasks」一欄除外),作答時也請用十六進位表示法輸入、輸出

所謂的十六進位表示法,指的是用一個只包含字元0~9和小寫a~f、由高位到低位的字串表示一個數,並且不能有前置的0(原數為0時則用一個0表示)。
例如03caf43AC都不是一個合法的十六進位表示法,而012345abcdef即是。

現在有$N$個不超過$M$位的數字$a_0,a_1,a_2,...,a_{N-1}$(兩兩有可能相同)。你要挑出$k\geq 1$個非負整數$0\leq b_0<b_1<b_2<\cdots<b_{k-1}<N$,使得$a_{b_0}\oplus a_{b_1}\oplus\cdots \oplus a_{b_{k-1}}=0$($\oplus$是XOR運算)。請求出你有幾種挑法。

Input Format

輸入第一行有一個正整數$N$,代表有幾個數字。
接下來有$N$行,每行有一個不超過$M$位的數字$a_i$。

對於所有測資,$1\leq N\leq 1200, 1\leq M\leq 400$。

子任務(測資) 額外限制 分數
1 (0~2) $N\leq 14, M\leq 10$ 9
2 (0~5) $N\leq 14$ 9
3 (6~9) $a_i\leq19$ 21
4 (0~10) 無限制 31

Output Format

輸出一行代表挑法個數。

Sample Input

5
2
5
7
a
d

Sample Output

3

Hints

範例輸入中,3組解分別是(2,5,7), (7,a,d), (2,5,a,d)。

要看清楚題目喔。

Problem Source

Problem Set by Yihda Yol

Subtasks

For Testdata: 0 ~ 2, Score: 9
For Testdata: 0 ~ 5, Score: 9
For Testdata: 6 ~ 9, Score: 33
For Testdata: 0 ~ 16, Score: 49
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 700 65536 262144
1 700 65536 262144
2 700 65536 262144
3 700 65536 262144
4 700 65536 262144
5 700 65536 262144
6 900 65536 262144
7 900 65536 262144
8 900 65536 262144
9 900 65536 262144
10 900 65536 262144
11 900 65536 262144
12 900 65536 262144
13 900 65536 262144
14 900 65536 262144
15 900 65536 262144
16 900 65536 262144