By Dhanadeepa_Red, history, 10 months ago, ,

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

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

•
• +1
•

 » 10 months ago, # | ← 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
•  » » 10 months ago, # ^ |   +1 Thanks brother.