问题: 不久前,巴特 (Bart) 做了一场关于树木的讲座。讲座结束后,巴特受到启发,想出了自己的树,他称之为 k-树。
k 树是无限根树,其中:
每个顶点恰好有 k 个孩子;
每条边都有一些重量;
如果我们查看从某个顶点到其子节点的边(正好是 k 条边),那么它们的权重将等于 1、2、3、...、k。
巴特的好朋友米尔豪斯一发现这棵树,立刻想知道:“从根开始,总共有多少条总权重为n(路径中所有边的权重之和)的路径一棵 k 树的,并且还包含至少一条权重至少为 d 的边?”。
帮助米尔豪斯找到问题的答案。由于方法的数量可能相当大,打印它模 1000000007 (10^9 + 7)。
输入数据 一行包含三个以空格分隔的整数:n、k 和 d(1 ≤ n,k ≤ 100,1 ≤ d_ _≤ k)。
输出数据 打印单个整数 - 问题的答案模 1000000007 (10^9 + 7)。
例子 输入示例 #1 content_copy 3 3 2 输出示例 #1 content_copy 3
解决: {
#include<iostream>
using namespace std;
long long n,k,d,MOD=1e9+7,dp[201][201];
int main(){
long long i,j,l,mx,ans=0;
cin>>n>>k>>d;
dp[0][0]=1;
for(i=0; i<=n; ++i)//+
for(j=0; j<=k; ++j)
for(l=1; l<=k; ++l){
mx=max(j,l);
dp[i+l][mx]=(dp[i+l][mx]+dp[i][j])%MOD;
}
for(i=d; i<=k; ++i)
ans+=dp[n][i], ans%=MOD;
cout<<ans<<'\n';
return 0;
}
}
我需要解释