302242: CF431C. k-Tree

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

k-Tree

题意翻译

## 题目描述 最近有一个富有创造力的学生Lesha听了一个关于树的讲座。在听完讲座之后,Lesha受到了启发,并且他有一个关于k-tree(k叉树)的想法。 k-tree都是无根树,并且满足: 1. 每一个非叶子节点都有k个孩子节点; 2. 每一条边都有一个边权; 3. 每一个非叶子节点指向其k个孩子节点的k条边的权值分别为1,2,3,...,k。 --------------- 当Lesha的好朋友Dima看到这种树时,Dima马上想到了一个问题:“有多少条从k-tree的根节点出发的路上的边权之和等于n,并且经过的这些边中至少有一条边的边权大于等于d呢?” 现在你需要帮助Dima解决这个问题。考虑到路径总数可能会非常大,所以只需输出路径总数 mod 1000000007 即可。(1000000007=10^9+7) ## 输入输出格式 ### 输入格式: 只有一行数,n,k,d. (1 <= n, k <= 100; 1 <= d <= k; n, d, k 三者用空格隔开)。 ### 输出格式: 只有一行,一个整数,即输出路径总数 mod 1000000007。

题目描述

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. 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. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF431C/83eea7df0a509cbc1e6d27ff0b5f74fa2e2e451c.png) 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 $ ?".Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).

输入输出格式

输入格式


A single line contains three space-separated integers: $ n $ , $ k $ and $ d $ ( $ 1<=n,k<=100; $ $ 1<=d<=k $ ).

输出格式


Print a single integer — the answer to the problem modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).

输入输出样例

输入样例 #1

3 3 2

输出样例 #1

3

输入样例 #2

3 3 3

输出样例 #2

1

输入样例 #3

4 3 2

输出样例 #3

6

输入样例 #4

4 5 2

输出样例 #4

7

Input

题意翻译

## 题目描述 最近有一个富有创造力的学生Lesha听了一个关于树的讲座。在听完讲座之后,Lesha受到了启发,并且他有一个关于k-tree(k叉树)的想法。 k-tree都是无根树,并且满足: 1. 每一个非叶子节点都有k个孩子节点; 2. 每一条边都有一个边权; 3. 每一个非叶子节点指向其k个孩子节点的k条边的权值分别为1,2,3,...,k。 --------------- 当Lesha的好朋友Dima看到这种树时,Dima马上想到了一个问题:“有多少条从k-tree的根节点出发的路上的边权之和等于n,并且经过的这些边中至少有一条边的边权大于等于d呢?” 现在你需要帮助Dima解决这个问题。考虑到路径总数可能会非常大,所以只需输出路径总数 mod 1000000007 即可。(1000000007=10^9+7) ## 输入输出格式 ### 输入格式: 只有一行数,n,k,d. (1 <= n, k <= 100; 1 <= d <= k; n, d, k 三者用空格隔开)。 ### 输出格式: 只有一行,一个整数,即输出路径总数 mod 1000000007。

加入题单

上一题 下一题 算法标签: