F - k-Tree

Codeforces Round #247 (Div. 2)

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 kedges), then their weights will equal 1, 2, 3, ..., k.

The picture below shows a part of a 3-tree.

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 (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).

Example
Input
3 3 2

Output
3

Input
3 3 3

Output
1

Input
4 3 2

Output
6

Input
4 5 2

Output
7

题意：对于一个k叉树，从根节点，有多少条路径长度为n，且路径上的路径最小值不小于d。k叉树边的权值从1到k

解法：dp算法，dp[i]为长度为i的路径的条数，长度为i可能是长度为i-1的路径加一，或i-2长度的路径加2，最小可能为i-k长度加k，因为是k叉树，最长边长度为k，所以dp[i]=dp[i-1]+dp[i-2]+......dp[i-k]，但是不能全部算上，因为这里包括所有边长度都小于d的，所以要把不和条件的减去。那么dp0[i]表示最长边不超过d的路径的数量，那么dp0[i]=dp0[i-1]+......+dp-[i-d]，dp[n]-dp0[n]即为所求答案

代码：

#include<iostream>
using namespace std;
long long dp[105];
long long dp1[105];
#define MOD 1000000007
int main()
{
    int n,k,d;
    cin>>n>>k>>d;
    dp1[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(i-j>=0){
                if(j<d)
                    dp1[i]+=dp1[i-j];
                else
                    dp[i]+=dp1[i-j];
                dp[i]+=dp[i-j];
                dp[i]%=MOD;
                dp1[i]%=MOD;
            }
        }
    }
    cout<<dp[n]<<endl;
}