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 \le A_i \le 100~

$2 \le K \le 100$ ~2 \le K \le 100~

Subtask 1 [19%]

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

$K = 2$ ~K = 2~

Subtask 2 [29%]

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

Subtask 3 [52%]

$1 \le N \le 10^5$ ~1 \le N \le 10^5~

Subtask 4 [0%]

Sample test cases.

Sample Input

4 2
1 7 2 9

Sample Output

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.

:)