It does. We do not use / in mod, we find the modular inverse for that. If mod is prime like {10}^{9}+7, modular inverse of k is {k}^{mod-2}. Read Fermat’s Little Theorem for this.
So the main idea is to realize is that whenever you get a component with odd length cycle, it gets stuck.Hence every unstuck component has only cycles of even length. It can be shown that Bipartite <=> Graph with even cycles only. That’s how the problem gets reduced to maintaining a DSU of bipartite components.
1 Like
Can you provide the test case in which storing 2 edges instead of 3 will fail!
If you have something like u -- 1 -- v -- (1,2,3) -- w -- 2 -- x , then if we store only 2 then we can get a sub optimal answer. But storing 3 makes sure that it’s always possible to mitigate it
Hi @vijju123 ,Kindly explain why (mod-1) is used, while calculating nCr() and mod is used while calculating power?
In response to:
Basically if you take the log of g(z), you can eliminate the factor of ci or m.
Hi @coldfire8549!
The coder has used Fermat’s Little Theorem.
a^(m-1)=1(mod m) when a and m are co-prime.
If you want to calculate a^b mod m where b is very large and you can calculate b only modulo some p, then you can do so by setting p= m-1.
Refer to my answer for NMNMX. Then solve the question which I gave there, i.e. 3-tower coloring. If unable to solve, look at its editorial. The answer lies there- Discover it yourself for best benefits 
Problem : Gears
For the query of type 3, speed depends only on u and v.
And the sign of answer depends on whether it is connected to other vertex by odd length or even length path. Because in the connected gear system there will be alternate +ve and -ve signs of answer from given vertex.
In short you have to color the graph in two colors.
I had maintained graph and used disjoint set data structure and array for gear teeth and when you have to change the teeth value you can just change value of array.
Maintain different color for each gear and when you connect two gears just change the color of other gear.
Note: Gears will be blocked when there is odd length cycle.
for query of type 3,
Suppose you have two components in which each components may contain several connected gears.
When query of type 2 occurs and you have to connect these two components then use disjoint set data structure and change the color of smaller component according to bigger components For e.g you had used colors 2,3 for 1st component and 4,5 for other component then change color of second component (if 2nd is smaller component).
while connecting two vertices from same component just check if one of them is blocked or by connecting these vertices will there be any odd length cycle ? i.e do they have same color ? because now you cant connect them if they have same color and after connecting they must have different colors hence all the vertices from component will be blocked.
Last while answering type 3 you can check color of both vertices if they are same color : use + sign answer else negative answer.
My solution https://www.codechef.com/viewsolution/19233845
1 Like
consider test case
n=7 m=6
edges (1,2),(1,3),(1,4),(2,5),(3,6),(4,7)
root has 3 children. each children have 1 children.
size of max clique is 2 but the answer for this is 3. Even I thought of max clique but rejected it because of this example. can someone explain what’s the correct answer?
The ans for any tree is 2
like in ur case i would place a cat at node 1,so now the cat can be in {2,5},{3,6},{4,7}
Lets say it was at 2,then i could place the second cat at 2,
similarly other cases can be handled as well
Basically at each time we restrict the mouse in a subtree
NMNMX:
For each element of the array, I calculated no. of subsequences in which that element was min and in which it was max by using simple nCr logic. Subtracted it from the total no. of subsequences of each element(same for each). Then raised that element to this no., which could be huge so used Modular Exponentiation.
I got 20 points(AC in subtask 1).
I’m getting Runtime error SIGFPE in subtask 2. Please help, I’m a beginner coder. Please help.
Here’s the link- https://www.codechef.com/viewsolution/19235686
Thanks.
Can someone share some good resources on Lichao segment tree and convex hull trick? Thanks in advance…
@vijju123 First thanks for the letting us know the new question 3-tower (atleast new for me) and I have done it. While going through your NMNMX editorial below I was not able to figure out how the total number of ways are {n-1} \choose {k-1}
Try the one at cp algorithm.
My bad I didn’t know that cats can see position of jerry. Maybe they should’ve given a test case to explain that.
1 Like
You have N elements out of which you have to choose k for sequence. Say I want to count contribution of an element A_i, then it means A_i MUST be in sequence. Now I have rest of N-1 elements out of which I have to choose k-1. This is (n-1)C(k-1) by definition.
1 Like
It is great way to clear doubts about different approaches for problems and share approaches in a thread form as it more interactive way.
1 Like
@megatron_64 : I am not fully convinced with this answer of yours.
Your entire explanation is based on an assumption: “Lets give vector 1 a magnitude of k/2 After the we have k - k/2 = k/2 magnitude left to be divided into n vectors.”