每日一题4月7日 树 乘法原理+思维

我太弱了。。
看了本题的题解，给大佬们跪下了。

题意：

有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。

思路：
如果要在树上解决这个问题，实在是太难处理了。
参考了题解。
首先我们可以想到，相同颜色的肯定是连续一段，不可能出现分开的两段。因此我们可以把问题转化为求x个连续段，换句话说，求x个连通块然后染k种颜色的问题。
因此我们枚举分成x个连通块，染k种颜色的话，一共有A(k,x)种情况。至于分x个连通块，其实就是删x-1条边，一共有n-1条边，我们存在C(x-1,n-1)种选择。那么我们把两个相乘就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
const int mod=1e9+7;
long long fac[333];
void init()
{
    fac[0]=1;
    for(int i=1;i<=300;i++)fac[i]=fac[i-1]*i%mod;
}
long long inv(long long x){
    int p=mod-2;
    long long ans=1;
    while(p){
        if(p%2)ans=ans*x%mod;
        p/=2;
        x=x*x%mod;
    }
    return ans%mod;
}
long long C(int n,int m){
    long long ans=fac[m]*inv(fac[m-n]*fac[n]%mod);;
    return ans%mod;
}
long long A(int n,int m){
    long long ans=fac[m]*inv(fac[m-n])%mod;
    return ans%mod;
}
int main()
{
    cin>>n>>k;
    init();
    long long ans=0;
    for(int i=1;i<=min(k,n);i++){
        ans+=C(i-1,n-1)*A(i,k)%mod;
        ans%=mod;
    }
    cout<<ans%mod<<endl;
    return 0;
}

当然，我们可以用dp解决，其实我们不需要关心树的结构，令dp[i][j]表示前i个节点染了j种颜色的方案数，那么下一个节点要么染同一种颜色，要么染新的颜***r>因此我们有dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(k-j+1)
这个复杂度是O(n^2)的。