![[ACM算法竞赛日常训练]DAY4题解与分析[树][子序列]| 组合数学 | 动态规划](/static/background/176.jpg "[ACM算法竞赛日常训练]DAY4题解与分析[树][子序列]| 组合数学 | 动态规划")
树（组合数学）
🎈 作者：Eriktse
🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈 原文链接（阅读原文获得更好阅读体验）：https://www.eriktse.com/algorithm/1095.html
树
通过观察条件“一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y，x到y的路径上的所有点的颜色都要与x和y相同。”我们可以发现，当且仅当染色的点可以全部连通时可以满足条件。
n个点划分为k块。
+ 1。
<= k即可，因为我们可以有一些颜色不使用。所以要划分为i块，只需要从n - 1条边中任选i - 1条进行删除即可，方案数是C(n - 1, i - 1。
i (i <= k个联通块，需要将i种颜色染上去，首先需要C(k, i种方法取出颜色，然后A(i, i一个全排列将颜色染上去。
$$ans=\sum_{i=1}^{k}C(n - 1, i - 1C(k, ii!$$
快速幂、乘法逆元的知识，需要自行学习。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 350, p = 1e9 + 7;
int fac[maxn];
int qmi(int a, int b
{
int res = 1;
while(b
{
if(b & 1res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}
int inv(int x{return qmi(x, p - 2;}
int C(int n, int m
{
if(n < m || n < 0 || m < 0return 0;
return fac[n] * inv(fac[n - m] * fac[m] % p % p;
}
signed main(
{
int n, k;scanf("%lld %lld", &n, &k;
fac[0] = 1;
for(int i = 1;i <= n; ++ ifac[i] = fac[i - 1] * i % p;
int ans = 0;
for(int i = 1;i <= n; ++ i//分为i块
{
int tmp = C(n - 1, i - 1 * C(k, i % p * fac[i] % p;
ans = (ans + tmp % p;
}
printf("%lld\n", ans;
return 0;
}
子序列
题目传送门：https://ac.nowcoder.com/acm/problem/17065
首先定义状态dp[i][j]表示以第i个元素结尾，且长度为j的序列的个数。
$${a_{p_i}}^{p_j} < {a_{p_j}}^{p_i}$$
$$ \frac{log(a_{p_i}}{p_i} < \frac{log(a_{p_j}}{p_j} $$
$$ b_i = \frac{log(a_{p_i}}{p_i} $$
对于选出的子序列中的每一个元素，他们满足一个偏序关系，只要我的b[j] > b[i]，那么b[j]将会大于所有的b[k] (k < i。
所以我们可以考虑以下的转移：