Блог пользователя strange14

How to Solve this DP problem?
Автор strange14, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить