Home Problem set Contests Submissions Rank list Discussions
Login

#3. 子段和 Partition sum

Memory limit: 256 MiB Time limit: 1000 ms Input file: stdin Output file: stdout
Problem type: traditional Judging mode: text compare
Uploded by root
Submit Submission record Statistics Test data Disscussions

Description

對於一整數序列 a = \{a_1,a_2\cdots a_n\} ，將 a 劃分成 m(m\geq 1) 段，其中第 i(1\le i\le m) 段為 a_{b_{i-1}+1},a_{b_{i-1}+2}, \dots, a_{b_i} ，且滿足 b_0=0,b_m=n 。

記 c_i 為第 i 段中所有數字按位與後的結果，即 c_i=a_{b_{i-1}+1}\land a_{b_{i-1}+2}\land \cdots \land a_{b_i} ，其中 x\land y 表示 x 與 y 按位與後的結果。求 \sum_{i=1}^m c_i 的最小值。

For a given integer sequence a = \{a_1,a_2\cdots a_n\} , it can be divided into m partitions, the i -th (1 \leq i \leq m) of which is a_{b_{i - 1} + 1}, a_{b_{i - 1} + 2}, \dots, a_{b_i} , where b_0 = 0 and b_m = n .

Denoting c_i=a_{b_{i-1}+1}\land a_{b_{i-1}+2}\land \cdots \land a_{b_i} , where " \land " represents the bitwise-and operator. You need to find the minimal value of \sum_{i=1}^m c_i .

Input

共 2T+1 行。

第一行一個整數 T ，表示數據組數。接下來的 2T 行，每兩行表示一組數據：第一行一個整數 n ，表示序列的長度，第二行 n 個整數，第 i 個整數表示 a_i 。

The input consists of many test cases.

The first line of the input contains an integer T , indicating the number of test cases.

In the following 2T lines, every two lines represent a test case. The first line contains an integer n , indicating the length of the sequence. The second line contains n integers, separated by spaces, the i -th of which indicates a_i .

Output

共 T 行，每行一個整數，分別表示每組數據的答案。

Write T lines in total; each line of the output contains an integer, indicating the answer to the corresponding test case.

Sample

Sample 1 input

1
2
0 1

Sample 1 output

0

Constraint and hint

對於所有測試數據，滿足 1 \leq T, n, \sum n\le 5\times 10^5,0\le a_i \le 2^{31} 。

子任務 分數 附加限制
1 20 T=1,n\le 100,a_i \leq 2^8
2 40 T=1,n\le 30000,a_i\le 2^{16}
3 10 a_i = 0
4 30 無附加限制

For all test data, 1 \leq T, n, \sum n\le 5\times 10^5,0\le a_i \le 2^{31} .

Subtask Score Additional Constraints
1 20 T=1,n\le 100,a_i \leq 2^8
2 40 T=1,n\le 30000,a_i\le 2^{16}
3 10 a_i = 0
4 30 No additional constraints
编辑器加载中 …
HKSCOJ Powered by SYZOJ.
Sponsored by Department of Computer Science, City University of Hong Kong.