| Submit | All submissions | Best solutions | Back to list |
DIVSEQ - DIVSEQ |
You're given two numbers - N and K (0 < N, K ≤ 1000). You have to count the number of sequences of positive integers with length N where every element must be not greater than K and for every two consecutive elements with indices i and i + 1 one of the conditions bellow must be true:
- a[i] is divisible by a[i + 1]
- a[i + 1] is divisible by a[i]
Input
On the only line you will be given the values of N and K.
Output
Print the number of the sequences described above modulо 1000000009.
Example
Input: 2 4 Output: 12
| Added by: | ivokaragyozov |
| Date: | 2016-03-03 |
| Time limit: | 0.200s-0.5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 GOSU JS-MONKEY |
| Resource: | http://www.math.bas.bg/infos/files/2013-05-02-C1.pdf |
hide comments
|
|||||
|
2024-07-13 06:33:21
CHECK: scanf,printf - got RE, cin,cout - got AC |
|||||
|
2021-09-28 08:24:30
Get Accepted in 1 go! : ) Nice dp problem. Last edit: 2021-09-28 08:25:24 |
|||||
|
2017-04-04 12:27:34 SUBHAM SANGHAI
Note, Mod is 10^9+9 not 10^9+7 |
|||||
|
2017-04-04 08:09:45
I am getting a runtime error on test case 15. I cannot figure out where did i go out of bounds. Can someone help?? Last edit: 2017-04-04 08:12:04 |
|||||
|
2016-03-09 17:18:44 darryl
Then what about the condition about consecutive integers a[i] and a[i+1] that must be true? When N=1, no such consecutive integers exist so this condition cannot be true. |
|||||
|
2016-03-09 10:49:10 ivo2001
Because when N = 1 every integer smaller or equal to K can be in the sequance so the answer is K |
|||||
|
2016-03-09 05:45:53 darryl
why when N=1, the answer is not 0? Last edit: 2016-03-09 05:46:39 |
|||||
|
2016-03-08 06:24:07
Here's a reword of the problem: You are given two integers, N and K. Both N and K are in the range of 1 to 1000 inclusive. Find the amount of integer sequences of length N where each integer in the sequence is both: 1) Less than or equal to K 2) Is divisible or a multiple of its adjacent neighbors. Hopefully, that makes it more clear for others who were confused like me. |
|||||
|
2016-03-04 10:09:28 ivo2001
Explanation of the example: The sequences must be of length 2 and they can only contain the numbers to 4, so the possible sequences are: [1, 1]; [1, 2]; [1, 3]; [1, 4]; [2, 1]; [2, 2]; [2, 4]; [3, 1]; [3, 3]; [4, 1]; [4, 2]; [4, 4]. But you can see that sequence [2, 3] is not correct because 2 is not divisible by 3 and 3 is not divisible by 2 |
|||||
|
2016-03-04 10:00:25 ivo2001
You must count the number of sequences A of length N where 1<=A[i]<=K and for every two consecutive elements - A[i] and A[i + 1] must be true A[i] is divisible by A[i + 1] OR A[i + 1] is divisible by A[i]. Last edit: 2016-03-04 10:00:41 |
|||||
RSS