计数类题目练习

感觉思路挺清晰的，先注意到只能 \(k-1\) 次划分，所以每种颜色必然在同一连通块。
树上简单路径唯一，所以可以想到将颜色相同的，先按照最短路径缩成一个点。加入存在某两种颜色的连通块有交，则此时必然无解。
缩成点后，则变成了，给定一棵树，分成 \(k\) 个连通块，每个连通块有且仅有一个颜色。
这个直接 DP 即可，我是设 \(dp_{u,0/1}\) 表示 \(u\) 往下走所在的连通块中是否存在有颜色的点，分类讨论进行转移即可。
时间复杂度 \(O(n\log n)\)，瓶颈在于 LCA。

注意到 \(n\) 虽然有 \(700\)，但是时限 10s 啊，所以考虑 \(O(n^3)\) 做法。
考虑把五元环拆成三段，长度依次为 2 2 1。那么我们先预处理出所有左端点为 \(l\)，右端点为 \(r\) 的，长度为 \(2\) 的链的数量，设为 \(f_{l,r}\)。
统计答案也就是枚举每一条边 \([u,v]\)，枚举一个点 \(mid\)，那么数量就是 \(f_{u,mid}\times f_{v,mid}\)。发现有很多重。
去重是容易的，这里就不写了。（懒）

首先考虑这个“最优策略”应该大概是什么样的。我们设 \(h\) 序列的最小值为 \(p\)，然后比 \(p\) 大的 \(h_i\) 与 \(p\) 的差的和为 \(s\)。可以比较容易的分讨几种情况。
那么我们可以设 \(dp_{i,p,s}\) 表示剩余 \(i\) 回合，此时最小值为 \(p\)，且多余出来的部分的和为 \(s\) 时，可以达成目标的最大概率。
分类讨论进行转移即可。

\[ dp_{i,p,s}=\begin{cases} 1&,i\ge 0\land p=1\land s=0\\ dp_{i-1,p-1,s}\times P+\max(dp_{i-1,p-1,n-1},dp_{i-1,p,s})\times (1-P)&,i>0\land p>1\land s=0\\ dp_{i-1,p-1,s}\times P+dp_{i-1,p,s-1}\times (1-P)&,i>0\land p>1\land s>0\\ dp_{i-1,p,s}\times P+dp_{i-1,p,s-1}\times (1-P)&,i>0\land p=1\land s>0\\ 0&,\text{otherwise} \end{cases} \]

我们发现这个是 \(O(nmV^2)\) 的，显然无法通过。
但我们发现，一旦 \(s\) 变为 \(0\) 后，后续的过程中 \(s\) 最大也只有 \(n-1\)。
并且根据上面的转移式子，很显然在 \(s>0\) 时的转移是唯一的，也就是最优策略是唯一的，我们直接对这一部分进行计算。
设 \(f_{i,j}\) 表示当前进行到第 \(i\) 回合，多余的和为 \(s\) 时的概率。容易得到答案等于 \(\sum_{i=s}^{m}f_{i-1,1}(1-P)dp_{m-i,\max(p-(i-s),1),0}\)。
\(f\) 的转移是容易的，这里就不说了。

观察限制条件以及题目中的图例，可以比较简单的发现，满足条件的树仅有两类。

1. 一颗“类”二叉树，仅有根可以有三个儿子。
   
2. 中间一条链，两端放两个二叉树（二叉树的根必须为两个儿子）。

至于边的方向，对于第一种情况，要么是一个内向树，要么是一个外向树。对于第二种情况，必须是一个内向树连向一个内向树。

好，我们接下来考虑计数即可。
我们先考虑第一种情况，我们发现根可以放三个很烦，所以不妨先也规定根也最多只能有两个儿子。
设 \(dp_{i}\) 表示最长有向路径的长度为 \(i\) 时的二叉树的数量，\(s_{i}=\sum_{j=0}^{i} dp_{j}\)。
分三种情况转移：

1. 根仅有一个儿子：\(dp_{i-1}\)。
   
2. 根有两个儿子，其中一个的有向最长路径的长度为 \(i-1\)，另一个小于 \(i-1\)：\(dp_{i-1}s_{i-2}\)。
   
3. 根有两个儿子，两个的有向路径长度均为 \(i-1\)：\(\dfrac{dp_{i-1}(dp_{i-1}+1)}{2}\)。

具体为什么要分这三种，以及每一种的贡献为什么是这么多，建议仔细思考一下。主要目的是去重。

至于最后的答案，我们根可以是三叉的，就比较麻烦啊，但依然可以分讨来做到不重不漏。

1. 根只有 1/2 个儿子：\(dp_{n}\)。
   
2. 根有 3 个儿子，且其中一个长度为 \(n-1\)，另外两个均小于 \(n-1\)：\(\dfrac{dp_{n-1}s_{n-2}(s_{n-2}+1)}{2}\)。
   
3. 根有 3 个儿子，且其中两个长度为 \(n-1\)，另外一个小于 \(n-1\)：\(\dfrac{s_{n-2}dp_{n-1}(dp_{n-1}+1)}{2}\)。
   
4. 根有 3 个儿子，且每个的长度均为 \(n-1\)：\(\dfrac{dp_{n-1}(dp_{n-1}+1)(dp_{n-1}+2)}{6}\)。

这几个的思路和前面 \(dp_{i}\) 的转移其实差不多。 因为树有两种方向，所以我们得乘 \(2\)，然后出现链的时候，两个方向是同构的，所以得减 \(1\)。

好，那我们第一类也就做完了。第二类怎么做呢？

首先，我们发现，假如两端的二叉树的根的儿子均为一个的话，那么中间这条链的长度有很多种方式组合，会出现很多重复。
于是我们不妨钦定一段的二叉树必须有两个儿子。值很显然也就是 \(dp_{i}-dp_{i-1}\)，前面转移弄懂了这一步是容易的。
另外一端的根为 1/2 个儿子均可。注意假如这一端为链的时候，也就变成第一种情况了，需要去掉。
那么贡献的答案也就很简单了，我们枚举一端有多长，另一端的长度也可以计算出来。

\[ \sum_{i=1}^{n-2}(dp_{i}-dp_{i-1})(dp_{n-1-i}-1) \]

（\(i=0\) 和 \(i=n-1\) 时，一个前者无意义，一个后者为 \(0\)，所以可以忽略。）

好，最后把两部分加起来就是答案了，时间复杂度 \(O(n)\)。

主要就是第二类斯特林数的一个式子，我记录在 trick 合集里面了，会的话就随便推出来了。

\[ \begin{aligned} &\sum_{i=1}^{n}\binom{n}{i}i^{k}\\ =&\sum_{i=0}^{n}\dfrac{n!}{i!(n-i)!}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\binom{i}{j}j!\\ =&\sum_{i=0}^{n}\dfrac{n!}{i!(n-i)!}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\frac{i!}{j!(i-j)!}j!\\ =&\sum_{i=0}^{n}\dfrac{n!}{(n-i)!}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\frac{1}{(i-j)!}\\ =&\sum_{i=0}^{n}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\dfrac{n!}{(n-i)!(i-j)!}\\ =&\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\sum_{i=0}^{n}\dfrac{(n-j)!}{(n-i)!(i-j)!}\times\dfrac{n!}{(n-j)!}\\ =&\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\dfrac{n!}{(n-j)!}\sum_{i=0}^{n}\binom{n-j}{n-i}\\ =&\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\dfrac{n!}{(n-j)!}2^{n-j}\\ \end{aligned} \]

直接 \(O(k^2)\) 预处理第二类斯特林数，\(O(k)\) 计算即可。
存在 \(O(k)\) 的做法。

和上面差不多一样推式子即可，最后一步是二项式定理，\(((m-1)+(1))^{n-j}\)。

\[ \begin{aligned} &\sum_{i=0}^{n}\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}i^k\\ =&\sum_{i=0}^{n}\binom{n}{i}\frac{(m-1)^{n-i}}{m^n}i^k\\ =&\frac{1}{m^n}\sum_{i=0}^{n}\binom{n}{i}(m-1)^{n-i}i^k\\ =&\frac{1}{m^n}\sum_{i=0}^{n}\dfrac{n!}{i!(n-i)!}(m-1)^{n-i}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\binom{i}{j}j!\\ =&\frac{1}{m^n}\sum_{i=0}^{n}\dfrac{n!}{i!(n-i)!}(m-1)^{n-i}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\frac{i!}{j!(i-j)!}j!\\ =&\frac{1}{m^n}\sum_{i=0}^{n}\dfrac{n!}{(n-i)!}(m-1)^{n-i}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\frac{1}{(i-j)!}\\ =&\frac{1}{m^n}\sum_{i=0}^{n}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}(m-1)^{n-i}\dfrac{n!}{(n-i)!(i-j)!}\\ =&\frac{1}{m^n}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\sum_{i=0}^{n}\dfrac{(n-j)!}{(n-i)!(i-j)!}\times\dfrac{n!}{(n-j)!}(m-1)^{n-i}\\ =&\frac{1}{m^n}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\dfrac{n!}{(n-j)!}\sum_{i=0}^{n}\binom{n-j}{n-i}(m-1)^{n-i}\\ =&\frac{1}{m^n}\sum_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\dfrac{n!}{(n-j)!}m^{n-j}\\ \end{aligned} \]