Can anyone explain me the implementation of the dp
1 Like
The dp state is f(i, j) which is, as the explanation says, the number of ways to choose some elements which are <= i from a, and their product has only those prime numbers in odd degree on whose index number j has 1 in binary representation.
Basically for f(i, j) you are given a limit i and a set of primes j. You have to calculate the number of ways in which one can choose any subset of the given a such that all the chosen numbers are \le i, and the set of primes appearing odd number of times in the product of the chosen subset is exactly j.
Let p_i be the set of primes appearing odd number of times in i. And let c_i be the number of times i occurs in a.
Now to calculate f(i, j), we can take i into a subset any number of times \le c_i, or not take it at all. Of course, if c_i = 0 then we have only one choice, not taking i. In that case f(i, j) = f(i-1, j).
But if c_i > 0, then think about how i affects the product of the subset.
- If we take i even number of times, then the primes appearing odd number of times in the product is unaffected by i since every prime factor of i will definitely occur even number of times. So this will contribute \text{ways to pick } i \text{ even times} \times f(i-1, j) to the total.
- But if we take i odd number of times, then the primes that appear odd number of times in i do have an effect, and may fill the required primes in j, or might add some primes that are not in j. This changes the set we call f(i-1, \cdots ) with from j to j \oplus p_i. So we calculate \text{ways to pick } i \text{ odd times} \times f(i-1, j \oplus p_i). If you’re wondering why xor operation is the right thing here, trying it with an example should help.
Now from combinatorics, \text{ways to pick } i \text{ even times} = \binom{c_i}{0} + \binom{c_i}{2} + \binom{c_i}{4} + ... = 2^{c_i - 1}. And \text{ways to pick } i \text{ odd times} is also 2^{c_i - 1}.
So finally,
f(i, j) =
\begin{cases}
1 & \text{if } i = 0 \text{ and } j = 0 \\
0 & \text{if } i = 0 \text{ and } j \ne 0 \\
f(i-1, j) & \text{if } c_i = 0 \\
2^{c_i - 1} (f(i-1, j) + f(i-1, j \oplus p_i) & \text{otherwise}
\end{cases}
The final answer is f(70, 0) - 1. The prime set is 0 because we don’t want any prime to appear odd number of times, and the -1 is to remove the empty subset which will always come in the answer.
Implementation here. This is different from the tutorial’s code in a few ways which I think makes it easier to understand. I have used the simple top-down approach whereas the tutorial’s code uses bottom-up dp that too in the “forward” manner. It’s a shame that the dp table in this code exceeds the small memory limit of 256 MB on Codeforces, so you will be forced to use a bottom-up solution where it is possible to optimize the memory usage by using only two rows instead of a table. It’s a nice problem combining many different ideas, so feel free to ask if any part of it is not clear!
5 Likes
I just got the first part of editorial in which we represent odd/even power(1 for odd and 0 for even) of primes in prime factorization of each integer in [1, 70] through a bitmask. After that I couldn’t understand a thing.
same thing