树

Solution

树上记数，dp[i][j]表示前i个位置上有j种颜色，那很自然就能推出dp[i][j] = dp[ i - 1 ][ j ] + ( k -
j + 1 )*dp[ i - 1 ][ j - 1 ]。
（dp[ i -1 ][ j ]是位置 i 和 i - 1 涂相同的颜色，( k - j + 1 ) * dp[ i - 1 ][ j - 1 ]是位置i和i-1涂不同颜色）

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e8
const int mod = 1e9+7;
const int maxn = 305;
#define iss ios::sync_with_stdio(false)
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll dp[maxn][maxn];
int main(){
    int n,k;
    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] + (k-j+1)*dp[i-1][j-1])%mod;
        }
    }
    ll ans = 0;
    for(int i = 1 ; i <= k ;++i) ans = (ans + dp[n][i])%mod;//位置n所有可能涂色的总和
    cout<<ans<<endl;
}