So I’m doing this problem, and my algorithm goes as follows:
Do a DFS to find for each node the number of ways to paint that node’s subtree black given that the node itself is black as well.
Do another DFS, this time taking into account the new painting configurations given by the parent.
My code is here. The problem is, since the mod is not necessarily prime, it’s impossible to do division, which is necessary for my algorithm to work.
My algorithm itself probably works, given that it AC’d on some hidden test cases as well as the sample ones.
How would I implement this algorithm without division? Or even better, is there a way of doing modulus division with composite primes that I don’t know of?
Well, you can in fact maintain a product such that you can recover the remainder when dividing by any of its multiplicands modulo M.
For example, if M=6 and P=6\cdot 11\cdot 13 \cdot 2, then we can represent P by the triple (2^2,3^1,5\pmod{6}). The first two terms correspond to the number of factors of 2 and 3 in P, and the last corresponds to all terms of the product that are relatively prime with 6.
If you want to find \frac{P}{6}\pmod{6}, then this would be represented by
So after some thinking, I managed to find a slightly different approach that doesn’t involve division. However, it does involve calculating the products of all the siblings of a child in \mathcal{O}(n).
A naive approach would be to simply keep a giant overhead product and get each of the sibling products through division. This would involve keeping keeping track of the overhead product without any modulus, which seems impossible without overflow.
EDIT: Yup, it overflowed. More test cases were passed, but not all of them. Proof here.