Algorithm
C. k-Tree
time limit per test
1 secondmemory limit per test
256 megabytesProblem link- https://codeforces.com/problemset/problem/431/C
input
standard inputoutput
standard outputQuite 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.
A k-tree is an infinite rooted tree where:
- each vertex has exactly k children;
- each edge has some weight;
- 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.
The picture below shows a part of a 3-tree.
Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (109 + 7).
Input
A single line contains three space-separated integers: n, k and d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).
Output
Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).
Examples
input
Copy
3 3 2
output
Copy
3
input
Copy
3 3 3
output
Copy
1
input
Copy
4 3 2
output
Copy
6
input
Copy
4 5 2
output
Copy
7
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
int const OO = 1e9 + 7;
int n, k, d, dp[101][2];
int calc(int sum, bool take) {
if(sum == n) return take;
if(sum > n) return 0;
int &ret = dp[sum][take];
if(ret != -1) return ret;
ret = 0;
for(int i = 1; i <= k; i++)
ret = (ret += calc(sum + i, (take || (i >= d)))) % OO;
return ret;
}
int main() {
scanf("%d%d%d", &n, &k, &d);
memset(dp, -1, sizeof dp);
printf("%d\n", calc(0, 0));
return 0;
}Input
3 3 2
Output
3
Demonstration
Codeforces Solution-k-Tree-Solution in C, C++, Java, Python