HCI '16 - Xorpow - Olympiads Online Judge

HCI '16 - Xorpow

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 0.6s

Memory limit: 256M

Authors:

zj97, damian, fanpu

Problem types

Who wouldn't love to have powers? Especially ones that are unique and exclusive?

Your task today is related.

Given an array $A$ $A$ of $N$ $N$ numbers, count the number of ranges that have an XOR-sum which is a positive power of $K$ $K$ . (XOR = eXclusive-OR).

Input Specification

The first line contains two integers, $N$ $N$ and $K$ $K$ , the number of integers and the base.

The second line contains $N$ $N$ space-separated integers, representing the numbers of the array.

Output Specification

The output should contain one line containing one integer, the number of ranges with a xor-sum that is a positive power of $K$ $K$ .

Constraints

For all subtasks:

$0 \le A_i \le 100$ $0 \leq A_{i} \leq 100$

$2 \le K \le 100$ $2 \leq K \leq 100$

Subtask 1 [19%]

$1 \le N \le 1\,000$ $1 \leq N \leq 1 000$

$K = 2$ $K = 2$

Subtask 2 [29%]

$1 \le N \le 1\,000$ $1 \leq N \leq 1 000$

Subtask 3 [52%]

$1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$

Subtask 4 [0%]

Sample test cases.

Sample Input

Copy

4 2
1 7 2 9

Sample Output

Copy

Explanation

The ranges are $\{2\}$ ${2}$ and $\{1, 7, 2\}$ ${1, 7, 2}$ .

Comments

9

max commented on April 8, 2018, 10:54 a.m. ← edit 4 →

How come kobortor has a score of 100/100, yet he is listed as having a wrong answer?

9

kobortor commented on April 10, 2018, 2:42 a.m.

:)