这题是一个树上二维dp
dp[i][j] 表示从某个叶节点出发包括i个点 涂j种颜***r>当你加一个点时只有两种方式 涂用过的 和 没用过的
涂同样的颜色只能跟父节点以上相同 所以为 dp[i-1][j]
涂不同的颜色可能从未涂过的颜色中选 所以为 (k-j+1)*dp[i-1][j-1]
注意随时取模
#include <bits/stdc++.h> #define ll long long using namespace std; ll const maxn=3e2+5; ll const mod=1e9+7; ll n,k,ans,dp[maxn][maxn]; ///dp[i][j] 表示从某个叶节点出发包括i个点 涂j种颜色 ///涂同样的颜色只能跟父节点以上相同 所以为dp[i-1][j] ///涂不同的颜色可能从未涂过的颜色中选 所以为 (k-j+1)*dp[i-1][j-1] int main(){ cin>>n>>k; dp[0][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) dp[i][j]=(dp[i-1][j-1]*(k-j+1)+dp[i-1][j])%mod; for(int i=1;i<=k;i++) {ans+=dp[n][i];ans%=mod;} cout<<ans<<endl; return 0; }