please wait
XOR DECOMPOSITION
Feb 7, 2019 at 12:42am
Somebody help me how to get started with this kind of problems.
Chef has a tree with N nodes (numbered 1 through N) and a non-negative integer x. The nodes of the tree have non-negative integer weights; let's denote the weight of node i by ai.
Next, let's define the XOR value of a tree as the bitwise XOR of weights of all its nodes.
Chef wants to remove zero or more edges from his tree in such a way that each individual tree in the forest formed by removing these edges has XOR value x. Help him compute the number of ways to remove a set of edges such that this condition is satisfied. Since the answer may be large, compute it modulo 109+7.
Input
The first line of the input contains two space-separated integers N and x.
The second line contains N space-separated integers a1,a2,…,aN.
Each of the following N−1 lines contains two space-separated integers u and v denoting an edge between nodes u and v in Chef's tree.
Output
Print a single line containing one integer ― the number of ways to remove edges, modulo 109+7.
Constraints
1≤N≤105
0≤x≤109
0≤ai≤109 for each valid i
1≤u,v≤N
Example Input
7 1
1 0 1 0 1 0 1
1 2
1 3
2 4
2 5
3 6
3 7
Example Output
5
Explanation
There are five valid ways to remove edges, splitting the tree into subtrees on nodes:
[1, 2, 3, 4, 5, 6] and [7] by removing the edge (3-7)
[1, 2, 3, 4, 6, 7] and [5] by removing the edge (2-5)
[2, 4, 5] and [1, 3, 6, 7] by removing the edge (1-2)
[2, 4, 5], [1], [3,6] and [7] by removing edges (1-2), (1-3) and (3-7)
[1, 2, 4], [5], [3,6] and [7] by removing edges (2-5), (1-3) and (3-7)
Chef has a tree with N nodes (numbered 1 through N) and a non-negative integer x. The nodes of the tree have non-negative integer weights; let's denote the weight of node i by ai.
Next, let's define the XOR value of a tree as the bitwise XOR of weights of all its nodes.
Chef wants to remove zero or more edges from his tree in such a way that each individual tree in the forest formed by removing these edges has XOR value x. Help him compute the number of ways to remove a set of edges such that this condition is satisfied. Since the answer may be large, compute it modulo 109+7.
Input
The first line of the input contains two space-separated integers N and x.
The second line contains N space-separated integers a1,a2,…,aN.
Each of the following N−1 lines contains two space-separated integers u and v denoting an edge between nodes u and v in Chef's tree.
Output
Print a single line containing one integer ― the number of ways to remove edges, modulo 109+7.
Constraints
1≤N≤105
0≤x≤109
0≤ai≤109 for each valid i
1≤u,v≤N
Example Input
7 1
1 0 1 0 1 0 1
1 2
1 3
2 4
2 5
3 6
3 7
Example Output
5
Explanation
There are five valid ways to remove edges, splitting the tree into subtrees on nodes:
[1, 2, 3, 4, 5, 6] and [7] by removing the edge (3-7)
[1, 2, 3, 4, 6, 7] and [5] by removing the edge (2-5)
[2, 4, 5] and [1, 3, 6, 7] by removing the edge (1-2)
[2, 4, 5], [1], [3,6] and [7] by removing edges (1-2), (1-3) and (3-7)
[1, 2, 4], [5], [3,6] and [7] by removing edges (2-5), (1-3) and (3-7)
Last edited on Feb 7, 2019 at 10:44am
Feb 7, 2019 at 7:17pm
It's impossible to help you because you aren't trying to help us.
Do you know what a tree is?
Do you know what an edge is?
Do you know what a forest is?
Do you know what bitwise XOR is?
Have you worked out an example on paper?
What have you done?
What are your thoughts?
Do you have any thoughts?
Do you know what a tree is?
Do you know what an edge is?
Do you know what a forest is?
Do you know what bitwise XOR is?
Have you worked out an example on paper?
What have you done?
What are your thoughts?
Do you have any thoughts?
Feb 7, 2019 at 7:37pm
I am not getting any idea to proceed.
Just now I thought of finding those which doesn't have xor equal to x.
I don't know whether I am thinking in right direction.
Just now I thought of finding those which doesn't have xor equal to x.
I don't know whether I am thinking in right direction.
Feb 7, 2019 at 7:43pm
its is unlikely that brute force will succeed. You are looking for some pattern you can exploit. You may want to start with the properties of xor. start small and on paper. xor like 5 values together and see what the resulting value looks like.
Feb 7, 2019 at 7:49pm
@jonnin
Tnx for the help I will try it.
But I don't think there would be pattern.
Tnx for the help I will try it.
But I don't think there would be pattern.
Last edited on Feb 7, 2019 at 7:50pm
Feb 7, 2019 at 8:15pm
but there are patterns to repeated xors. look at a single bit.
a bunch of ones xored is 0 if there are an even number of them, and 1 for an odd number:
1^1 = 0
1^1^1 = 1
1^1^1^1 = 0... etc
it may not help you. But as I said, there is something you need to find that avoids brute force.
a bunch of ones xored is 0 if there are an even number of them, and 1 for an odd number:
1^1 = 0
1^1^1 = 1
1^1^1^1 = 0... etc
it may not help you. But as I said, there is something you need to find that avoids brute force.
Feb 8, 2019 at 12:01am| Dumb wrote: |
|---|
| Yeah thinking but couldn't find anything at all. |
Then you either aren't thinking very well or this problem is beyond you.
Try something simpler.
Feb 8, 2019 at 2:36pm
Did anyone get passed with the basic cases for the problem XDCOMP ?
Topic archived. No new replies allowed.