这个问题可以用动态规划来解决。

设 $dp[n][is]$ 表示在 k 叉树中，总路径长度为 $n$ 的路径数量，其中：

• 若 $is = 1$，表示路径中存在一条长度至少为 $d$ 的边；
• 若 $is = 0$，表示路径中所有边的长度都小于 $d$。

初始状态：$dp[0][0] = 1$。

状态转移：枚举可以作为路径第一条边的所有边，然后问题转化为相同的问题，只是剩余路径长度更小（因为走到子节点后，其子树仍然是一棵 k 叉树）。

转移公式如下：

• 对于 $dp[n][0]$（所有边权都小于 $d$）：

$$dp[n][0] = dp[n-1][0] + dp[n-2][0] + \dots + dp[n - \min(d-1, n)][0] $$

• 对于 $dp[n][1]$（至少有一条边权 $\ge d$）：

$$dp[n][1] = dp[n-1][1] + dp[n-2][1] + \dots + dp[n - \min(d-1, n)][1] + \big(dp[n-d][0] + dp[n-d][1]\big) + \dots + \big(dp[n - \min(n, k)][0] + dp[n - \min(n, k)][1]\big) $$

更多细节请参考具体实现代码。

时间复杂度：$O(nk)$

注意，这个解法可以很容易地通过预处理前缀和优化到 $O(n)$ 复杂度。不过对于本题来说，$O(nk)$ 的解法已经足够，不需要进一步优化。

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

const int mod = 1e9 + 7;

int dp[100][2];

void add(int &a, int b)
{
    a += b;
    if(a >= mod)
        a -= mod;
}

int main(int argc, char ** argv)
{
    int n, k, d;
    cin >> n >> k >> d;
    dp[0][0] = 1;
    dp[0][1] = 0;
    
    for(int i = 1 ; i <= n ; ++i)
    {
        dp[i][0] = dp[i][1] = 0;
        
        for(int j = 1 ; j <= k ; ++j)
        {
            if(i-j < 0) break;
            
            if(j < d)
            {
                add(dp[i][0], dp[i-j][0]);
                add(dp[i][1], dp[i-j][1]);
            }
            else
            {
                add(dp[i][1], dp[i-j][0]);
                add(dp[i][1], dp[i-j][1]);
            }
        }
    }
    cout << dp[n][1] << "\n";
    return 0;
}