codeforces k-Tree (dp仍然不会耶)

题目
题意: 给定一棵树，每个节点恰好有k个儿子，对应的边恰好为1-k. 求一下有多少种方案，满足路径上的权值恰好为n，且至少有一个边满足边权>=d.
思路: 其实就是个线性dp，每一层只能选1-k.好久没dp就d不出来了，可以先dp一遍1-k都能用的，再dp一遍只能用1-(d-1)的，相减就是满足题意的.f[0][i][j]: 用全部边，从前i层中选，边权恰好为j的方案数。只需枚举当前这一层用多少权值，即可递推出。f[0][i][j] = f[0][i-1][j-1…k]
只依赖于上一层，所以可以把i这一维给压缩掉。f[0][j] = f[0][j-1…k]
时间复杂度: O(n* n * k)或O(n*k)
代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 102;
const int mod = 1e9+7;
int n,m,k,T;
int f[2][N]; //0:所有边,1:小于d的边,f[j]:权值为j的方案数
void solve()
{
    
	cin>>n>>k>>m;
	f[0][0] = 1;
		for(int j=1;j<=n;++j) //权值
		{
    
			for(int t=1;t<=k;++t) //枚举从哪转移
			{
    
				if(j-t<0) break;
				f[0][j] = (f[0][j] + f[0][j-t]) % mod;
			}
		}
	k = m-1;
	f[1][0] = 1;
		for(int j=1;j<=n;++j) //权值
		{
    
			for(int t=1;t<=k;++t) //枚举从哪转移
			{
    
				if(j-t<0) break;
				f[1][j] = (f[1][j] + f[1][j-t]) % mod;
			}
		}
	long long ans = 0;
	ans = (ans + f[0][n]) % mod;
	ans = (ans - f[1][n]) % mod;
	ans = (ans + mod) % mod;
	cout<<ans;
}
signed main(void)
{
    
	solve();
	return 0;
}