HCI '16 - Xorpow

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 256M

Authors:
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 of N numbers, count the number of ranges that have an XOR-sum which is a positive power of K. (XOR = eXclusive-OR).

Input Specification

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

The second line contains 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.

Constraints

For all subtasks:

0 \le A_i \le 100

2 \le K \le 100

Subtask 1 [19%]

1 \le N \le 1\,000

K = 2

Subtask 2 [29%]

1 \le N \le 1\,000

Subtask 3 [52%]

1 \le N \le 10^5

Subtask 4 [0%]

Sample test cases.

Sample Input

4 2
1 7 2 9

Sample Output

2

Explanation

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


Comments


  • 8
    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?


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

      :)