牛客网练习1---树（组合）

这道题在博主自己看来，其实和树没有多大关系（不知是不是数据的问题），反正我是这样处理的把这个树看成一个链有n个节点，有k个颜色，要连续的涂，则有公式：牛客网练习1---树（组合）

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
const int maxn = 3000 + 10;

int n, k;
ll c[maxn][maxn];
ll a[maxn];
ll ans;

int main(){
    cin >> n >> k;
    c[0][0] = 1;
    for (int i = 1; i <= 300; ++i)
    {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j-1] + c[i - 1][j]) % mod;
    }
    a[0] = 1;
    for (ll i = 1; i <= 300; ++i)
        a[i] = a[i - 1] * i%mod;

    for (int i = 1; i <= min(n, k); ++i){
        ll A = c[n - 1][i - 1];
        ll B = c[k][i] * a[i] % mod;
        ans = (ans + A*B%mod) % mod;
    }
    cout << ans << endl;
}

牛客网练习1---树（组合）

相关推荐