codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

431C.md (1556B)


      1 Source: https://codeforces.com/problemset/problem/431/C
      2 
      3 C. k-Tree
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Quite recently a creative student Lesha had a lecture on trees. After the lecture Lesha was inspired and came up with the tree of his own which he called a *k*-tree.
     22 
     23 A *k*-tree is an infinite rooted tree where:
     24 
     25 * each vertex has exactly *k* children;
     26 * each edge has some weight;
     27 * if we look at the edges that goes from some vertex to its children (exactly *k* edges), then their weights will equal 1, 2, 3, ..., *k*.
     28 
     29 The picture below shows a part of a 3-tree.
     30 
     31 ![](https://espresso.codeforces.com/5f44e910ac6f25b7db3084c9a710bdc243bed406.png)
     32 
     33  As soon as Dima, a good friend of Lesha, found out about the tree, he immediately wondered: "How many paths of total weight *n* (the sum of all weights of the edges in the path) are there, starting from the root of a *k*-tree and also containing at least one edge of weight at least *d*?".
     34 
     35 Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (109 + 7).
     36 
     37 Input
     38 
     39 A single line contains three space-separated integers: *n*, *k* and *d* (1 ≤ *n*, *k* ≤ 100; 1 ≤ *d* ≤ *k*).
     40 
     41 Output
     42 
     43 Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 3 3 2
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 3
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 3 3 3
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 4 3 2
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 6
     81 ```
     82 
     83 Input
     84 
     85 ```
     86 4 5 2
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 7
     93 ```