Can anyone explain me the implementation of the dp
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,
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!
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