【每日一题】树（组合数学)

我们要考虑的是把这棵树分成最多min(n,k)个块，因为要保证每个块颜色不同最多有k种颜色，所以不能超过k，又因为最多有n个点，所以也不能超过n，因此最多分min(n,k）个块。
如果知道这个思路就好做了，我们只要分的块数用组合数公式 C(k,x)表示从k种颜色里挑出来x种颜色，C(n-1,x-1)表示从n-1条边选x-1条边，表示如何把这棵树分为x块。最后乘上x!表示这x种颜色的染色顺序，就能得到最终答案啦。
为了简化运算，我们事先写一个循环把jc数组表示出来，jc[i]代表i的阶层。算的时候不要忘记取模，就可以快乐ac啦~

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const ll mo=1e9+7;
ll n,k;
const ll N=350;
ll jc[N];
ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mo;
        a=a*a%mo;
        b>>=1;
    }
    return res;
}

ll ans;
ll c(ll n,ll m)
{
    return jc[n]*qp(jc[m]*jc[n-m]%mo,mo-2)%mo;
}
signed main()
{
    cin>>n>>k;
    jc[0]=jc[1]=1;
    for(int i=2;i<=300;i++)
        jc[i]=jc[i-1]*i%mo;
    for(int i=1;i<=min(n,k);i++)
    {
        ans+=c(n-1,i-1)*c(k,i)%mo*jc[i]%mo;
        ans=ans%mo;
    }

    cout<<ans<<endl;
    return 0;
}