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)\text{ 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\text{ 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\text{ is }u\text{'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\text{ and }m=m, where \text{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)\text{ 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)\text{ 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)\text{ and }d=d” be further simplified? Yes! Note that x\text{ and }y=0 is a sufficient condition for (x+y)\text{ 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)\text{ and }y=y. Thus “(\Delta-1+d)\text{ and }d=d” is equivalent to “(\Delta-1)\text{ and }d=0”.
Let Z_d be the bitwise-xor sum of Y_f's such that f\text{ and }d=0. For a query \Delta we directly output Z_{(\Delta-1)\bmod 2^{18}}, since 2^{18}>N and ((\Delta-1)\text{ 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\text{ xor }2^i}&i\text{-th bit of }j\text{ is }1\\ dp_{i,j}\text{ xor }dp_{i,j\text{ xor }2^i}&i\text{-th bit of }j\text{ 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.
nice problem !