×

# Dp codeforces div2

 1 1 http://codeforces.com/problemset/problem/895/C Can anyone explain me the implementation of the dp asked 30 Nov '17, 17:08 23●5 accept rate: 0% 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. (30 Nov '17, 17:18) same thing (30 Nov '17, 17:32)

 5 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! answered 01 Dec '17, 08:31 6★meooow ♦ 6.5k●5●17 accept rate: 49%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,754
×220
×8
×4

question asked: 30 Nov '17, 17:08

question was seen: 818 times

last updated: 01 Dec '17, 09:06