Kilonova
Toggle theme

infO(1) Cup 2024 Mirror - Day 1 | XORsecv

This was the problem page during the contest. Access the current page here.
Time limit: 0.3s Memory limit: 512MB Input: Output:

XORnelius is the greatest mathematician in the Info(1)cup Kingdom. One day he stumbled upon a very interesting algorithmic task. But instead of solving it, which would have been easy for him, he decided to give it to you as a test.

Task

You are given an array a0,a1,…,aN−1a_0, a_1, \dots , a_{N−1} of numbers. For a contiguous subsequence (i,j)(i, j) of this array, we calculate the XORvalue of the sequence using the following steps:

  1. We create an array bb of size k=j−i+1k = j − i + 1, so that b0=ai,b1=ai+1,…bk−1=ajb_0 = a_i, b_1 = a_{i+1}, \dots b_{k−1} = a_j.
  2. The XORvalue is equal to the sum of the values (bi⊕i)P(b_i \oplus i)^P, for all 0≤i<k0 ≤ i < k, where we denote with ⊕\oplus the operator XOR.

Calculate the sum of the XORvalues of all contiguous subsequences of the array, modulo 109+710^9 + 7.

Formally, if we let f(i,j)f(i, j) denote the XORvalue of sequence (i,j)(i, j), we have that

f(i,j)=∑m=0j−i(ai+m⊕m)Pf(i, j) = \sum_{m = 0}^{j - i} (a_{i + m} \oplus m)^P

You are asked to find the following value

∑i=0N−1∑j=iN−1f(i,j) (mod 109+7)\sum_{i = 0}^{N - 1} \sum_{j = i}^{N - 1} f(i, j) \ (mod \ 10^9 + 7)

Your task is to solve this problem and prove to XORnelius that you are as great of a mathematician as he is.

Input data

The first line of input contains NN, denoting the size of the array, and PP. The second line contains
values a0,a1,…,aN−1.a_0, a_1, \dots , a_{N−1}.

Output data

The only line of output must contain the required answer.

Restrictions

  • 1≤N≤250 0001 \leq N \leq 250 \ 000
  • 1≤P≤1 000 000 0001 \leq P \leq 1 \ 000 \ 000 \ 000
  • 0≤ai≤2180 \leq a_i \leq 2^{18}, pentru 0≤i<N0 \leq i < N
# Points Restrictions
1 7 N≤100,P=1N \leq 100, P = 1
2 8 N≤1 000,P=1N \leq 1\ 000, P = 1
3 12 N≤1 000N \leq 1 \ 000
4 15 P=1P = 1
5 12 N≤50 000,ai<8N \leq 50 \ 000, a_i < 8, for all 0≤i<N0 \leq i < N
6 14 N≤50 000,P=2N \leq 50 \ 000, P = 2
7 32 No further restrictions.

Example 1

stdin

3 3
3 2 4

stdout

556

Explanations

The XORvalues of all the contiguous subsequences in the array are written below:

  • i=0,j=0:b={3},f(0,0)=(3⊕0)3=33=27i = 0, j = 0: b = \{3\}, f(0, 0) = (3 \oplus 0)^3 = 3^3 = 27
  • i=0,j=1:b={3,2},f(0,1)=(3⊕0)3+(2⊕1)3=33+33=27+27=54i = 0, j = 1: b = \{3, 2\}, f(0, 1) = (3 \oplus 0)^3 + (2 \oplus 1)^3 = 3^3 + 3^3 = 27 + 27 = 54
  • i=0,j=2:b={3,2,4},f(0,2)=(3⊕0)3+(2⊕1)3+(4⊕2)3=33+33+63=27+27+216=270i = 0, j = 2: b = \{3, 2, 4\}, f(0, 2) = (3 \oplus 0)^3 + (2 \oplus 1)^3 + (4 \oplus 2)^3 = 3^3 + 3^3 + 6^3 = 27 + 27 + 216 = 270
  • i=1,j=1:b={2},f(1,1)=(2⊕0)3=23=8i = 1, j = 1: b = \{2\}, f(1, 1) = (2 \oplus 0)^3 = 2^3 = 8
  • i=1,j=2:b={2,4},f(1,2)=(2⊕0)3+(4⊕1)3=23+53=8+125=133i = 1, j = 2: b = \{2, 4\}, f(1, 2) = (2 \oplus 0)^3 + (4 \oplus 1)^3 = 2^3 + 5^3 = 8 + 125 = 133
  • i=2,j=2:b={4},f(2,2)=(4⊕0)3=43=64i = 2, j = 2: b = \{4\}, f(2, 2) = (4 \oplus 0)^3 = 4^3 = 64

The sum of all these values is equal to 556556 modulo 109+710^9 + 7.

Example 2

stdin

7 1
4 2 3 6 5 7 11

stdout

379

Example 3

stdin

6 2
1 3 15 7 15 31

stdout

9410

Log in or sign up to be able to send submissions!