http://codeforces.com/problemset/problem/895/C Can anyone explain me the implementation of the dp asked 30 Nov '17, 17:08

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. 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 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(i1, j) & \text{if } c_i = 0 \\ 2^{c_i  1} (f(i1, j) + f(i1, 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 topdown approach whereas the tutorial's code uses bottomup 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 bottomup 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! answered 01 Dec '17, 08:31

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