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)
0 700 65536
1 700 65536
2 700 65536
3 700 65536
4 700 65536
5 700 65536
6 900 65536
7 900 65536
8 900 65536
9 900 65536
10 900 65536
11 900 65536
12 900 65536
13 900 65536
14 900 65536
15 900 65536
16 900 65536