PREFXOR Editorial

editorial
, , ,
1

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

f_k[i] = f_{k-1}[0] \oplus f_{k-1}[1] \oplus .....f_{k-1}[i]

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

1 Like
2

Why do you take problems from AtCoder and not acknowledge it?

2 Likes
3

hello, could you show me the link of this problem on atcoder, thx

4

Is it exactly same? I have probably seen similar problem/logic (the combinatorial part) but it works for only n<=1e6. I (including the testers and many others I have referred) have not seen the extension to n<=1e18.

Can you once attach the link of the problem?

5

Source problem from AtCoder

6

T7 original problem

7

In fact, I have seen this question in many places, not only on ATC.

8

The main ideas of binomial coefficients and using Lucas’s theorem to transform into submask condition are the same. The AtCoder problem then adds additional complexity on top of that by requiring you to do subset-sum dp.

Also, you are overcomplicating the solution to this version with your dp because one can immediately tell if a given bit is on or off using the submask condition. Check my submission for more details: CodeChef: Practical coding for everyone

To prove that it works simulate the process up to k = x = 16 and print the results bit-by-bit. You will see that each bit forms Pascal’s triangle mod 2 shifted by (-2^{bit}, 2^{bit}). Then apply Lucas’s theorem the same way you did.

I have probably seen similar problem/logic (the combinatorial part) …

As you can see, in my solution there is only the combinatorial part, which is the same. That’s why I think that problem is too similar to ARC 137 D to be used in a rated contest.

10

Simple combinatorics and induction seriously? Atleast give some hint bro.

Can anyone explain how to prove this? Any hint is also appreciated

11

@adityagamer Visualize a two-dimensional grid where k is a row index, and x is a column index. You’ll see that each element is the xor of the elements directly above and to the left of it. Then each entry j of the first row contributes to a given table entry f_k[i] as many times as many paths there exist from (0, j) to (k, i). This is nothing but the mentioned binomial coefficient.

3 Likes
12

@sky_nik

  1. I could not find any resource on this corollary of Lucas theorem. Can you share please?

  2. On cp-algorithms the time complexity for Binomial coefficient using Lucas theorem is mentioned O(m + log n) Binomial Coefficients - Algorithms for Competitive Programming (cp-algorithms.com)
    But everywhere I see any implementation its in O(m^2 + logn). Can you please share some resources of (m+logn) ?

13

  1. So Lucas’s theorem states \binom{m}{n} = \prod_i \binom{m_i}{n_i} \pmod{p}. For p = 2 we have m_i, n_i \in \{0, 1\}, and \binom{m_i}{n_i} = 0 \iff (m_i = 0) \land (n_i = 1). Hence \binom{m}{n} = 1 iff no such bit i exists, i.e. if n is a submask of m.

  2. Precompute i! and 1/i! modulo m in O(m) time, then \binom{x_i}{y_i} = \frac{x_i!}{y_i! (x_i - y_i)!} can be computed in O(1) time and we have \log_m n digits.

1 Like
15

Thank you so much bro.

16

Oh your soln is very nice. Sorry we missed this. We thought that combinatorial part might be slightly well known and our soln involved unnecessary dp which was slightly complicated. We will take more care while choosing future problems.

17

Issoke, results show that my solution was very easy to miss. I just happened to see 3 problems on Lucas’s theorem in a short period of time and it felt weird. Another nice problem that I’ve seen is RainbowConnection from TopCoder.