每日一题 4.7 树

这题是一个树上二维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;
}