k-Tree

ll dp[N][N][2];//深度i 总权值为j 是不是存在权值大于d的边..然后随便转移就好了...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=105;
ll dp[N][N][2];//深度i 总权值为j 是不是存在权值大于d的边.
int main()
{
    ll n,k,d;
    cin>>n>>k>>d;
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++)//层数.
    {
        for(int j=0;j<=n;j++)//总权值.
        {
            for(int l=1;l<=min(k,n);l++)//转移参数.
            {
                if(j+l>n) continue;
                dp[i][j+l][1]+=dp[i-1][j][1];
                if(l>=d) dp[i][j+l][1]+=dp[i-1][j][0];
                if(l<d)  dp[i][j+l][0]+=dp[i-1][j][0];
                dp[i][j+l][0]%=mod;
                dp[i][j+l][1]%=mod;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++) ans=(ans+dp[i][n][1])%mod;
    cout<<ans<<endl;
    return 0;
}