计数类题目练习

先注意到只能 \(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} \]

首先需要观察性质，得出一些结论。

1. 一个合法的染色方案一定有 \(n\) 个白色和 \(n\) 个黑色。
   
2. 假设不存在全黑或者全白的骨牌，则合法的方案一定为左侧全黑/全白，右侧相反。
   
3. 假设存在 \(k\) 块全白/黑，则一定有 \(k\) 块对应的全相反颜色的骨牌，并且剩下的位置在满足第一条下可随意安排。

有了这三条结论后，就很简单了。
假设初始情况有 \(a\) 个白色，\(b\) 个黑色。假如初始存在全黑/白，那么可行方案数为 \(\dbinom{2n-a-b}{n-a}\)，这是容易理解的。
假如不存在呢，那么我们需要减掉不合法的方案，也就是填完所有问号后，依然不存在全黑/白的骨牌，并且不满足第二条的方案数。
容易发现上述不合法方案数为 \(2\) 的全问号骨牌数的幂。
最后再加上可能出现的第二条即可。
难点主要在观察性质。
注意求组合数的不合法情况。

时间复杂度 \(O(n)\) 或者 \(O(n\log n)\)，区别在于求解阶乘的逆元。

正如题名所说，这道题一眼看过去，确实感觉就很 classical。
我们知道 \(\operatorname{lcm}(a,b)=\dfrac{ab}{\gcd(a,b)}\)，所以可以很自然的想到，枚举 \(gcd\) 的值，然后去找到除掉 \(\gcd\) 后乘积最大的两个互质的数，这俩会贡献一个答案。
那么现在问题来了，怎么找到这俩值。

暴力做显然是不行的，时间复杂度会是 \(O\left(\sum\limits_{i=1}^{V}\left(\dfrac{V}{i}\right)^2\right)\)，显然在 \(i=1\) 的时候就已经 \(V^2\) 了，不可接受。

接下来也可以比较自然的想到，从大到小枚举，当前枚举到 \(x\)，假如 \(x\) 与前面枚举过的一个数 \(y\) 互质，那么对于满足 \(x<z<y\) 的数 \(z\)，在后面一定不会产生贡献。
那么我们可以维护一个栈，如果对于当前的 \(x\) 存在这么一个 \(y\)，则一直弹栈到 \(y\) 即可。

那么问题还是在于，怎么知道当前栈内是否存在与 \(x\) 互质的数 \(y\)。这是你要是依然暴力，显然复杂度还是不变的。

考虑容斥。令 \(p(x)\) 为 \(x\) 的质因子集合，可以写出式子 \(\sum\limits_{s\in p(x)} (-1)^{\left|s\right|} cnt_{\prod\limits_{i\in s}i}\)。其中 \(cnt_{x}\) 表示数列中为 \(x\) 的整数倍的数的数量。
我们发现这个是难以计算的，但我们可以联想到 \(\mu(x)\)，我们发现 \(\mu(x)\) 的定义，恰好满足我们的需求。
于是式子改写为 \(\sum\limits_{d\mid x}\mu(d)cnt_{d}\)。非常的简洁，并且只需要 \(d(x)\) 的时间就可以判断是否存在互质的数。

于是我们只需要先预处理出 \(1\) 到 \(V\) 的每个数的因子，这个是 \(O(n\log n)\) 的，然后枚举 \(\gcd\) 的值，照着上文说的那样做就行了，时间复杂度 \(O(V\log^2 V)\)，其实就够了。

但这样未免麻烦了，我们根据 \(\operatorname{lca}\) 的式子，可以知道，一定存在 \(a,b\) 满足 \(\gcd(a,b)=1,a\mid A,b\mid B,\operatorname{lca}(A,B)=\operatorname{lca}(a,b)\)。于是我们直接将输入的所有数的因子拿出来，去个重，跑一遍就可，时间复杂度也就是 \(O(V\log V)\)，也很好写。

注意细节有点多，比如假如你像我一样先把所有因子丢进去，sort 一下再 unique 一下的话，那么你最大需要开 \(128\) 倍的空间。

首先注意到他算的是平方的异或，所以大概率只能先求出这 \(2^{24}\) 种情况各自的答案后，再算答案。
然后我们发现，假如对于一个元音集合 \(s\) 可以使得单词 \(a\) 合法，那么对于 \(s\) 所有的超集 \(S\) 都是合法的，所以这启示我们只需要找出最小的合法情况，再对每个集合算其子集的和即可。
每个单词还有个小小的容斥，每个单词很短，可以直接暴力枚举可能性对每种状态设置初值即可。那么此时复杂度为 \(O(3^24)\) 显然无法通过。
有个经典的 trick，枚举子集的和可以使用高维前缀和做到 \(O(n2^n)\)，不会的可以去学一下。那么就做完了，不知道为啥有 2700，可能因为这道题是 div1 的 E 吧。
时间复杂度 \(O(24\times 2^{24})\)。

一眼看过去会想到枚举 \(\operatorname{lca}\)，然后用 DP，怎么怎么转移之类的，但你会发现，合并信息的时候，你需要二项式定理，并且你记录状态肯定需要记录选了几个点，空间都炸了，更别说时间。
好，我们发现 \(k\) 只有 \(200\)，很小。并且这个恰好是 \(a^b\) 的形式，我们将其拆一下。（这里也就是题解的第一步，偷瞟了一眼就会了xwx，但我觉得正常做很难想到拆这个啊。）

\[ \begin{aligned} &\sum_{X\subseteq{1,2,\dots,n},X\not =\varnothing}(f(X))^k\\ =&\sum_{X\subseteq{1,2,\dots,n},X\not =\varnothing}\sum_{i=0}^{k}\begin{Bmatrix}k\\ i \end{Bmatrix}\binom{f(X)}{i}i!\\ =&\sum_{i=0}^{k}\begin{Bmatrix}k\\ i \end{Bmatrix}i!\sum_{X\subseteq{1,2,\dots,n},X\not =\varnothing}\binom{f(X)}{i}\\ \end{aligned} \]

后面的组合数可以看作，选出一些边集，从中选出 \(i\) 条边的方案数。
这个显然可以设 \(dp_{i,j}\) 表示，当前考虑到 \(i\) 为根的子树，其中所有可能的选出的点的集合构成的虚树中选出 \(j\) 条边的方案数。

这个的转移显然是 \(dp_{u,i}=\sum_{j=0}^{i}dp_{u,j}dp_{v,i-j}\)。
但是具体的实现中有很多细节，视实现方式不同细节可能也会不同，所以我这里就不展开了，仔细想想什么情况需要去掉，什么情况不需要去掉就行了。

主要其实还是推式子……
我们不妨设同一种整数的位置为 \(p\) 数组，那么对于这一种整数贡献的答案也就是：\(\sum\limits_{i=1}^{c}\sum\limits_{j=i}^{c}p_{j}-p_{i}\)。
我们发现对于单一位置 \(p_{i}\)，贡献的值为：\(p_{i}(i-1-(c_{i}-i))=p_{i}(2i-c_{i}-1)\)。
于是我们将所有 \(\sum c_{i}\) 个数按照括号里的这一块排序，有一个显然的贪心：按排序结果从大到小依次从 \(n\) 到 \(1\) 赋编号。
至于方案数，排序值相同的显然对于任意一种排列方式均是可以的，乘上若干个阶乘就行了。

这样直接做的复杂度是 \(O(\sum c_{i})\) 的，会爆。
我们发现对于排序值相同的，其实贡献是排序值乘上一个等差数列的和，所以直接拿个桶存一下，加上一个差分就好了。
时间复杂度 \(O(V)\)。