首先，01 背包是 NP 的，直接做不行，要关注题中的小性质。

发现 $C_i\le 300$，于是对 $C_i$ 分组，同组内价值降序排序，设为 $V_1\sim V_m$，那么如果选上 $V_k$，则必然选上 $V_1\sim V_{k-1}$，挺显然的。把它看作一个前缀和的形式。

然后发现 dp 方程可以各个同余类分开计算。

进一步的，一个同余类中的 dp 转移具有决策单调性。

感性理解一下，如果决策不具有单调性，那么会取的 $k$ 会更大，而我们对元素进行了降序排序，$k$ 更大是不优的。

决策单调性分治计算即可。

时间复杂度 $\mathcal O(kc\log k)$。

Editorial of srf.

不知道状压可不可行阿，先说一个我的错误状压思路：

设 $f(i,S)$ 表示前 $i$ 个点的叶子节点状态为 $S$，最大深度在点 $i$ 处取得的方案数。然后会发现这个东西没办法转移。

继续瞎搞，考虑枚举深度 $d$，划分为若干层，进行状压 dp，但是仍然没啥好方法转移。也可能是我菜。

树上深度计数考虑组合数。计算总数，最后除以 $(n-1)!$。

设 $f(i,j)$ 表示 $i$ 个点的树，深度为 $j$ 的方案数。

因为点 $2$ 一定接在 $1$ 上，所以我们枚举点 $2$ 的子树大小及深度，然后合并其它子树和点 $2$ 的子树。这样显然不会算重。

这个过程可以保证方案是合法的，只关心点编号之间的大小关系。用组合数辅助计算。

取整可以用 long double 或者 __int128 存一下。

时间复杂度 $\mathcal O(n^4)$。

观察一下样例，不难发现答案单调不升。且注意到，一对点对 $(i,j)$ 至多贡献一次。

因此我们猜想，若 $G_k$ 中 $(i,j)$ 有贡献，则 $G_{k-1}$ 中 $(i,j)$ 仍有贡献。这不难证明（好像 [CSP-S 2021] 廊桥分配 也有这种思想）。

上述性质可以引出一个更强的判定条件，继续进行扩展，发现图 $G$ 中 $(i,j)(i\le j)$ 有贡献当且仅当存在两条路径 $P:i\to j,Q:j\to i$ 使得 $P,Q$ 中经过的编号最小的点编号 $\ge i$。

这条性质有点隐蔽，但证明非常简单，考虑反证法，假设有一个点 $k$ 在 $i\to j$ 的路径上，使得 $k\lt i$，那么就存在 $k\to j$ 和 $j\to i\to k$ 两条路径，则 $(k,j)$ 对答案产生贡献，$k$ 已被删除，与假设相悖。原命题成立。

然后我们考虑计算答案。根据上述性质，我们可以倒着加边，枚举判断每个点对最早在何时联通，然后后缀和计算答案。

但是这样是 $\mathcal O(n^2m)$ 的，考虑优化。

一种方法是直接倒序 Floyd，中途判断答案，但 $\mathcal O(n^3)$ 的复杂度很卡常，坏。

（不过这题数据比较水，其实也很难卡满复杂度，lg 题解中看到，似乎倒序加边跑 dijkstra，用斐波那契堆就可以过。）

考虑优化判断联通性的过程。枚举点 $i$，计算所有 $(i,j)(j\ge i)$ 的贡献。

发现 $(u,v)$ 在原图联通，等价于 $v$ 在原图和反图均可达 $u$。

将原图反图分开计算。先考虑原图上加入一条边 $u\to v$ 的影响。

发现若 $u,v$ 原本都与 $i$ 联通，则 $u\to v$ 这条边无意义，扔掉。

反之，若 $v$ 原本不联通，分情况讨论：

若 $u$ 原本联通，则 $v$ 本身和它所连的点变为联通状态。bfs 一遍即可。

反之，$u\to v$ 这条边以后可能产生贡献，先保存下来。

反图类似处理，显然 bfs 过程中答案会发生变化，途中计算即可。

不难发现这样每条边只会被遍历 1 次，故时间复杂度 $\mathcal O(n(n+m))$。稍有卡常，但问题不大。还有能完美通过本题的 bitset 做法，但是我学不会 /ll。

upd：新增了 bitset 的代码，具体做法可以去 Alex_Wei 老师的题解 中学习。

考虑分别计算恰有 $i$ 中颜色恰出现 $S$ 次的方案数，记为 $f_i$，则答案为 $\sum_{i=0}^{m}{f_i w_i}$。

直接算 $f_i$ 不好算，考虑至少有 $i$ 中颜色恰出现 $S$ 次的方案数，记为 $g_i$，显然，

$$g_i = C_{m}^{i} \frac{n!}{(n - iS)! (S!)^i} (m - i)^{n - iS}$$

式子中的三项分别表示： “选出 $i$ 种颜色”，“选位置让这 $i$ 种颜色恰出现 $S$ 次”，“其余的随便填剩下的颜色”。

这个式子是会算重的。具体的，对于一种恰有 $j(j \ge i)$ 种颜色恰出现 $S$ 次的方案，它在 $f_i$ 中会被算 $C_j^i$ 次。于是，

$$g_i = \sum_{j=i}^{m}{C^i_j f_j}$$

根据二项式反演有，

$$f_i = \sum_{j=i}^{m}{C^i_j g_j (-1)^{j-i}}$$

至此我们有了 $O(m^2)$ 的算法。

二项式反演是可以化成卷积形式的，

$$f_i = \sum_{j=i}^{m}{C^i_j g_j (-1)^{j-i}}$$

$$\rightarrow \quad f_i = \frac{1}{i!} \sum_{j=i}^{m}{\frac{j!}{(j-i)!} g_j (-1)^{j-i}}$$

下边懒得打这个 $\frac{1}{i!}$。

令 $A_i = i!g_i \, , \, B_i = \frac{(-1)^{i}}{i!}$ 则，

$$f_i = \sum_{j=i}^{m}{A_{j} B_{j-i}}$$

这里涉及差卷积，令 $A'_i = A_{m-i} \, , \, f'_i = f_{m-i}$ （也就是翻转）则，

$$f'_{m-i} = \sum_{j=i}^{m}{A'_{m-j} B_{j-i}}$$

再令 $t=j-i$ 有，

$$f'_{m-i} = \sum_{t=0}^{m-i}{A'_{m-i-t} B_{t}}$$

也就是，

$$f'_{i} = \sum_{t=0}^{i}{A'_{i-t} B_{t}}$$

这就是标准卷积形式，使用 $NTT$ 即可。$(1004535809=479 \times 2^{21} +1)$

值得注意的是，上述变形没有用到关于 $f_i$ 或 $g_i$ 的性质，于是对任何二项式反演均成立。

首先很容易想到差分约束

一个条件相当于 $x_i-x_j\le w(i,j)\iff x_i\le w(i,j)+x_j$，考虑从 $j$ 到 $i$ 连边，边权为 $w(i,j)$

考虑某个 $x_i-x_j$ 最小是多少，发现其实就是图中 $i\to j$ 的最短路的相反数。

因此，设 $\text{dis}(i,j)$ 表示 $i\to j$ 的最短路长度，那么我们只需要找到 $\min_{j\neq i}\text{dis}(i,j)$ 即可。

考虑分治。定义 $\text{solve}(l,r)$ 表示计算 $[l,r]$ 内每个点对 $[l,r]$ 内自己的贡献；设 $mid=(l+r)/2$，我们建一个源点 $s$ 并向每个 $x\in[l,mid]$ 连边，从 $s$ 开始跑 SPFA，就算出了 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。

同理也可以算出 $[mid+1,r]$ 到 $[l,mid]$ 的贡献；分治的边界是 $l=r$，此时直接返回即可。可以发现分治完成之后，我们就算出了 $[1,n]$ 中每个点的答案。

代码实现的方式大概是对每一位分 $0,1$ 考虑，和分治本质是等价的。

代码并不难写，不到 100 行，一张图就能截下来

COGS 不支持 Markdown，有些格式用不了，推荐到我的博客阅读。

Observation 1：从大到小，遇到 1 就操作，这样的操作次数最少。

证明：显然。

Observation 2：设上述结论得出的操作序列为 $p_1\sim p_m$，则对于每一次随机操作，如果操作的 $i\in p$，则 $m\gets m-1$，反之 $m\gets m+1$。

证明：因为操作顺序不影响结果，所以若 $i\in p$，则最少操作次数 -1。

反之手动模拟，如果 $i\notin p$，那么操作序列就要新增 $i$，操作次数 +1。

也就是说，答案只和 $m$ 的大小有关。

据此，设 $f_i$ 表示当前状态最少操作次数为 $i$ 时的期望答案。

有：

$$\begin{cases}f_i=i, & i\le k\\f_i=\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1, & \rm Otherwise\end{cases}$$

不知道有没有 MO 大神能解这个函数方程阿，反正我搞不出来这个东西，讲一下在洛谷题解里看到的神奇方法。

（upd：看到一种叫线性高消的神奇做法，算是高斯消元的变种，因为每个方程只有 3 项，所以可以 $\mathcal O(n)$ 算出来方程组的解）

考虑转化为更一般的形式，通常来讲期望递推都可以化简为 $f_i=f_{i-1}+b_i$ 的形式。

那么不妨设 $b_i=f_i-f_{i-1}$ 即 $f_i=f_{i-1}+b_i$，其中 $b_i$ 未知，把它带进方程解出来：

$$\begin{aligned}f_i & =\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1\\& = \frac{i}{n}(f_{i}-b_i)+\frac{n-i}{n}(f_i+b_{i+1})+1\end{aligned}$$

化简得：

$$b_i=\frac{(n-i)b_{i+1}+n}{i}$$

显然，$f_n=f_{n-1}+1$，故 $b_n=1$，先递推出 $b$，然后再推 $f$ 即可。

因为要求 $1\sim n$ 的约数，故时间复杂度为 $\mathcal O(n\ln n)$