# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Narhan Kamzabek

Tester: Jakub Safin, Satyam

Editorialist: Pratiyush Mishra

# DIFFICULTY:

3078

# PREREQUISITES:

Bitwise Operations, Dynamic Programming

# PROBLEM:

Chef has an array A such that A_i = i.

A *transform* on the array is performed by replacing each element of the array with the bitwise XOR of the prefix till that element. For example, if B denotes the array after performing *transform* on array A, then, B_i = A_1 \oplus A_2 \oplus \ldots \oplus A_i. Similarly, if C denotes the array after performing two *transforms* on array A, then, C_i = B_1 \oplus B_2 \oplus \ldots \oplus B_i.

Let f^K be the array obtained by performing K *transforms* on the array A. Thus, f^K_X denotes the X^{th} element of the K^{th} transform of the array A.

Formally,

- f^0_i = A_i
- f^1_i = A_1 \oplus A_2 \oplus \ldots \oplus A_i
- f^2_i = f^1_1 \oplus f^1_2 \oplus \ldots \oplus f^1_i
- f^k_i = f^{k-1}_1 \oplus f^{k-1}_2 \oplus \ldots \oplus f^{k-1}_i. Here, \oplus denotes the bitwise XOR operation.

Given K and X, determine the value f^K_X.

# EXPLANATION:

Basically in this problem, we need to calculate f_k[i]. By definition

Using simple combinatorics and induction, we can prove that f_k[i] is just XOR of all 1 \leq j \leq i such that \binom{k+i-j}{k} is odd.

This is a well known fact as a corollary of Lucas Theorem that \binom{k+i-j}{k} is odd if and only if k is a submask of (k+i-j).

Now we need to find XOR of all j such that 1 \leq j \leq i and (k+i-j) is a supermask of k.

We can do it using dp[bit][carry][0/1] which defines the XOR of all j if we processed the first bit bits, carry is a carry bit for (k+i-j) that we have after processing bit bits, and the last parameter is 0 if j \leq i or 1 otherwise.

Now we go through bits, if the current bit of k is 0, we can try to make a bit of (k+i-j) equals to 0 or 1, and if the current bit of k is 1, then the bit of (k+i-j) should also be 1.

# TIME COMPLEXITY:

O(logK), for each test case

# SOLUTION:

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution