http://codeforces.com/problemset/problem/414/B
Can anyone help me in understand the problem.Just need explaination.Thanks in advance
http://codeforces.com/problemset/problem/414/B
Can anyone help me in understand the problem.Just need explaination.Thanks in advance
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Name |
---|
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.
Let 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 —
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
Thanks brother.