NC13611

题意

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

思路

把题目转化为给你一颗n结点的树，将其分成个连通块涂上不同的颜色，此时发现染色方案的数量与这棵树的形状无关，仅与k和n有关，将其看为一个点集，每个点集可以涂一种颜色。

  2. 组合数学：分成个连通块可看做断条边，则可选边的方案数为C_{n-1}^{i-1}，每一个块可以取的颜色有种，又可以将连通块分为块不同颜色，最后总的方案数

DP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 300 + 5;

ll n,k,f[N][N],res;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            f[i][j]=(f[i-1][j]%mod+f[i-1][j-1]*(k-(j-1))%mod)%mod;
        }
    }
    for(int i=1;i<=k;i++){
        res=(res+f[n][i])%mod;
    }
    cout<<res<<'\n';
    return 0;
}

组合数学

下面的代码还可以用求线性逆元来优化到O(n)，由于我是个蒟蒻现在还不会所以这里未优化复杂度为

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 300 + 5;

ll n,k,res,p=mod;

ll qpow(ll a,ll b){
    ll res=1;
    for(;b>0;b>>=1,a=a*a%mod)
        if(b&1) res=res*a%mod;
    return res;
}

inline ll C(ll n,ll m){
    if(n<m) return 0;//组合数n<m特判
    if(m>n-m) m=n-m;//组合数性质
    ll a=1,b=1;
    for(int i=0;i<m;i++){
        a=a*(n-i)%p;//组合数分子 a 
        b=b*(i+1)%p;//组合数分母 b
    } 
    return a*qpow(b,p-2)%p;//费马小定理 a/b=a*b^(p-2) 
}

inline ll A(ll n,ll m){
    if(n<m) return 0;
    ll a=1;
    for(int i=n-m+1;i<=n;i++){
        a=a*i%p;
    } 
    return a;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=min(n,k);i++){
        res=(res+C(n-1,i-1)*A(k,i)%mod)%mod;
    }
    cout<<res<<'\n';
    return 0;
}