A.

先把原串的答案算出来，枚举哪一位反转，判断是不是要减一即可，复杂度 。

code

B.

考虑分类讨论：

1. 当  时，有 ，这部分直接加到  即可；
2. 当  时，有 ，这部分直接加到  即可；
3. 当  时，有 ，这部分直接加到  即可；
4. 否则有 ，有 ，这部分直接加到  即可。

复杂度 。

code

C.

考虑先算低于  位的数字有多少。我们把数字看成长为  的序列，然后统计差分序列的数量即可。考虑枚举差分序列之和 ，然后通过插板法，可以得到答案是：

考虑差分，得到最终答案是：

使用 lucas 定理计算组合数即可，复杂度 。

code

D.

考虑一个暴力的贪心做法：第一组的左端点一定是 1，直接二分找到最后一个满足题目限制的右端点 ，答案加一；然后把现在左端点设为 ，重复操作......这样是  的。

考虑在确定一个独立的组的时候，使用倍增规约二分。先使用倍增算法，从  开始枚举 ，一次性加入  条边，直到不满足题意。这样可以确定这一组的右端点在某个  内的边内，然后再在这个区间内暴力二分即可。

考虑这样做的复杂度：加边的过程和二分都是  的，也就是说可以花  的时间确定一个大小为  的组，因此总复杂度 。

code

E.

考虑先把所有询问离线，然后从小到大枚举询问右端点，用某种数据结构维护每个左端点的答案。

考虑对于一个点，只保留最后一次覆盖它的线段，并把这个点的权值记为线段的标号。

考虑把相邻的权值相同的点合并成同一段来维护，段的权值就是这些点的权值。那么新加入一条线段，就相当于合并（或者说删除）它覆盖到的旧的段，把这些段的权值变成当前枚举到的右端点。

当然可能有一些段会被当前线段从中截断，这种段至多有两个，可以先把它们分解成两段。于是我们可以假定新加入的线段覆盖到的每个段都是完整的。

对应在统计答案的数据结构上，如果合并了一个权值是  的段 ，相当于数据结构上  这个区间的答案整体加上段  的长度，其中  是当前的右端点。由于询问是单点询问，因此可以用树状数组来维护差分数组实现区间修改（或者直接使用线段树），这一部分就是  的。

考虑如何维护出覆盖了哪些线段。可以使用 set 来维护每两个连续段之间的分界点，每次暴力合并连续段即可。根据均摊理论，总复杂度就是 。

code

F.

把每个联通块看成一个点，我们会得到一张完全图，而我们要求的是一个生成树。因为  的取值只跟度数序列有关，可以考虑枚举上面这张图的每个点的度数序列 ，然后用这个序列构造生成树的 Prufer 序列，可以得到 Prufer 序列的个数是：

把点的度数分配到原图上，得到方案数是：

加权之后就是：

我们需要对所有可能的  序列求上式的值的和，序列应该满足 ，且所有  之和为 ，且序列长度恰好为 。

先把所有  减一，然后考虑对每个  构造生成函数 ，那么答案即是 。

这样暴力卷积就是  的了。

考虑优化，设 ，答案变成 。有推导：

根据麦克劳林展开式，我们知道后面的  的  次系数应该是  再乘上原来的系数。形式化的，有等式：

这样就只需要对每个  算出后面的求和的值，直接计算可以做到 ，应该足够通过本题。

考虑构造 ，那么有：