Submit solution

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

Authors:
Problem types
Allowed languages
C, C++

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 a XOR-sum which is a positive power of K. (XOR = eXclusive-OR).

Input Format

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 Format

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

Subtasks

For all subtasks, 0 \le A_i \le 100; 2 \le K \le 100.

Subtask 1 (19%): 1 \le N \le 1000; K = 2.

Subtask 2 (29%): 1 \le N \le 1000.

Subtask 3 (52%): 1 \le N \le 10^5.

Subtask 4 (0%): Sample Testcases.

Sample Input

4 2
1 7 2 9

Sample Output

2

Explanation

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


Comments


  • 6
    max  commented on April 8, 2018, 6:54 a.m. edit 4

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


    • 5
      kobortor  commented on April 9, 2018, 10:42 p.m.

      :)