Анонсирован VK Cup 2018! Регистрация уже идет! Приглашаем ознакомиться с информацией о Чемпионате на его странице. ×

Автор Dhanadeepa_Red, история, 6 месяцев назад, ,

http://codeforces.com/problemset/problem/414/B

Can anyone help me in understand the problem.Just need explaination.Thanks in advance

•
• +1
•

 » 6 месяцев назад, # | ← Rev. 3 →   0 A sequence is called good if all the numbers are divided by its previous number(excluding the first number ofcourse). So a sequence like — 1,4,12,36 is called good but 1,4,8,14 is not good.Now you will be given n (the maximum number you can use in the sequence) and k (length of sequence). You have to tell how many sequences can be made out of these restrictions. Solution HintLet dp[k][cur] be the number of good sequences with k numbers that ends with cur. So — Recurrence : From a number cur we can move to all the divisors of cur. Say the divisors of cur are — x1, x2, x3, ... xn. Then our recurrence will look like — `dp[n][cur] = dp[n-1][x1] + dp[n-1][x2] + ... dp[n-1][xn]`Base case : It's easy to tell that base case is for n = 1. (Figure out what you have to do then)Now you only need to find a good way to store all the divisors of the numbers from 1 to 2000. You can see my code if you get stuck : 27958781
•  » » 6 месяцев назад, # ^ |   +1 Thanks brother.