strange14's blog

How to Solve this DP problem?
By strange14, history, 3 years ago, In English

1559E - Mocha и звезды

Tutorial uses mobius function to solve this problem. How can we solve this using DP, as I have seen many people use it in their solutions.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Let $$$dp[i]$$$ be the number of ways with $$$\gcd = i$$$.

If you calculate it in descending order of $$$i$$$, $$$dp[i] =$$$ (number of ways with values multiples of $$$i$$$) — $$$\sum_{k=2}^{\lfloor m/i \rfloor} dp[ik]$$$.

You can check out similar techniques in this blog.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got this bit, thanks! I was looking at your solution 125973986 Just wanted to know if you're storing in kn[i][j] : number of ways after i terms and upto jth multiple of g, or something else?

    → Reply