### PROBLEM LINK:

**Author:** Bogdan Ciobanu

**Tester:** Jingbo Shang

**Editorialist:** Hanlin Ren

### DIFFICULTY:

Medium-hard

### PREREQUISITES:

binomial coefficients, Lucas’s theorem, multidimensional prefix sum

### PROBLEM:

You are given a rooted tree with root number 0. Every node u has a weight X_{0,u}. When d>0, define X_{d,v} is the bitwise-xor sum of all X_{d-1,u} where u is in v's subtree. You are also given Q queries, each query is a number \Delta, and you need to output X_{\Delta,0}.

### QUICK EXPLANATION:

Let Y_d be the xor-sum of weights of all nodes whose depth is exactly d, then the answer to a query \Delta is the xor-sum of all Y_d's, where (\Delta-1) ext{ and }d=0. By using a dp technique similar to multidimensional prefix sum, one can compute Z_d, which means the xor-sum of all Y_k's where k ext{ and }d=0, in O(N\log N) time, and the query takes only constant time.

### EXPLANATION:

##subtask 1

Since N,\Delta\le 500, we can calculate X_{i,u} for all 0\le i\le 500, 0\le u < N. Given X_{i,0},X_{i,1},\dots,X_{i,N-1}, we can compute X_{i+1,0},X_{i+1,1},\dots,X_{i+1,N-1} by doing one dfs on tree. This gives an O(N\cdot\max\Delta) algorithm.

##other subtasks

Let’s first consider, what if “xor” is changed to addition? i.e., what if X_{i+1,u} is defined as the sum, rather than xor, of all X_{i,v}'s where v is in u's subtree? Obviously the answer is a linear combination of all weights, i.e., X_{\Delta,0}=\sum_{u=0}^{N-1}f(\Delta,u)X_{0,u}, where f(\Delta,u) is something only dependent with \Delta and u.

### What is f(\Delta,u)?

**TL;DR**: f(\Delta,u)=\binom{dep_u+\Delta-1}{\Delta-1} where dep_u is u's depth and dep_0=0.

Now let’s consider how to solve f(\Delta,u). Take the sample input as an example:

Then we have:

For example, f(2,3)=3 and f(2,2)=6 here.

A recurrence equation of f is: f(\Delta,u)=\sum_{v ext{ is }u ext{'s ancestor}}f(\Delta-1,v)(note that v could be u). Why? Note that when we calculate X_{\Delta,0}, we write

This explains the above equation.

Let’s do more on the equation:

Thus, f(\Delta,u) is the number of sequences (v_0,v_1,v_2,\dots,v_{\Delta}) such that:

- v_0=u;
- v_{\Delta}=0(note that f(0,v)=[v=0]);
- For all 1\le i\le\Delta, v_i\uparrow v_{i-1}.

Obviously all v_i's appear on the path from u to 0. Let dep_x be the depth of node x(dep_0=0) and d_i=dep_{v_{i-1}}-dep_{v_i}, then (d_1,d_2,\dots,d_{\Delta}) is an array satisfying the following condition:

- d_i's are nonnegative integers;
- \sum_{i=1}^{\Delta}d_i=dep_u.

We find that every array d satisfying the above condition gives us a unique valid sequence v! So f(\Delta,u) is just the number of such array d's. Next is a classical lemma stating this number is just \binom{dep_u+\Delta-1}{\Delta-1}(refer to Wikipedia, the last line of “Definition and interpretations”). We omit the proof here.

*Lemma 1: given n,k, the number of nonnegative solutions of x_1+x_2+\dots+x_n=k is \binom{n+k-1}{n-1}.*

### Coming back to XOR

Now let’s consider the xor case. Note that xoring the same number for even times does nothing, so for a query \Delta, we pick all nodes u such that f(\Delta,u) is odd, and xor them up. Next we’ll use a lemma called Lucas’s Theorem:

*Lemma 2: given n,m,p, and p is a prime. Let’s write n,m in base p:*

*Then,*

Let me demonstrate the lemma by an example. Let p=5, n=116, m=55. Then n=(\overline{431})_5,m=(\overline{210})_5, so \binom{n}{m}\equiv \binom{4}{2}\cdot\binom{3}{1}\cdot\binom{2}{0}\equiv 3\pmod 5. Actually, you can check that \binom{n}{m}=5265169722428127562717416598795968\equiv 3\pmod 5.

How does the theorem help us? Note that we only need to know the reminder \binom{a}{b}\bmod 2 for some huge a,b. When p=2, Lucas’s theorem becomes

*Lemma 3: \binom{n}{m}\equiv 1\pmod 2 if and only if n ext{ and }m=m, where ext{and} is the bitwise-and operation.*

Thus, f(\Delta,u)\equiv 1\pmod 2\iff \binom{\Delta-1+dep_u}{dep_u}\equiv 1\pmod 2\iff (\Delta-1+dep_u) ext{ and }dep_u=dep_u.

### subtask 2

To solve subtask 2, we preprocess Y_d as the bitwise-xor sum of all nodes at depth exactly d, and for a query \Delta we enumerate all d from 0 to N, if (\Delta-1+d) ext{ and }d=d, we xor the answer with Y_d.

Time complexity: O(NQ).

### subtask 3

If you print the values of X_{i,0} and try to find patterns, you’ll find that X_{i,0} has a period of length L\le 2N. The solution for this subtask is: first find the length of that period L, then prepare all X_{i,0}'s for i\le L; for any query \Delta, we just print X_{\Delta\bmod L,0}.

In the solution of subtask 4 I’ll show that, the answer only depends on the last \lceil\log_2 N\rceil bits of \Delta-1, and that’s why we have an O(N) period.

### subtask 4

Can the condition “(\Delta-1+d) ext{ and }d=d” be further simplified? Yes! Note that x ext{ and }y=0 is a sufficient condition for (x+y) ext{ and }y=y, since when adding x and y in binary, no carries would happen. Is it necessary? The answer turns out to be yes! This can be proved by contradiction: Suppose i is the lowest bit that both x and y has 1 on this bit. Then (x+y)'s i-th bit is 0 and that violates (x+y) ext{ and }y=y. Thus “(\Delta-1+d) ext{ and }d=d” is equivalent to “(\Delta-1) ext{ and }d=0”.

Let Z_d be the bitwise-xor sum of Y_f's such that f ext{ and }d=0. For a query \Delta we directly output Z_{(\Delta-1)\bmod 2^{18}}, since 2^{18}>N and ((\Delta-1) ext{ and }d) is only related to (\Delta-1)'s last 18 bits.

How to compute Z_d? We can do it by a dp that’s similar to multidimensional prefix sum: Let dp_{i,j} denote the bitwise-xor sum of all Y_d's, such that:

- For 0\le k < i, d and j's k-th bit can’t be both 1;
- For i\le k < 18, d and j's k-th bit are the same.

Then dp_{i+1,j}=\begin{cases} dp_{i,j ext{ xor }2^i}&i ext{-th bit of }j ext{ is }1\\ dp_{i,j} ext{ xor }dp_{i,j ext{ xor }2^i}&i ext{-th bit of }j ext{ is }0\\ \end{cases}. Note that dp_{0,j}=Y_j, and what we want is Z_j=dp_{18,j}.

The overall complexity is O(N\log N+M).

### ALTERNATIVE SOLUTION:

If your solution is different with ours, feel free to leave a comment.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.