T1
经典 trick，将 nmodm=S(m) 转化为 n−⌊mn⌋×m=S(m)，继而变成 n−S(m)=⌊mn⌋×m。由于 S(m)≤81，所以考虑暴力枚举 S(m)。右式两个值均为整数，可以再次暴力枚举左式的约数当作 m，检查式子是否合法。
时间复杂度 O(81×9×n)。
T2
不难发现答案 ≤2。分类讨论一下。
-
答案为 0，直接判断即可。
-
答案为 1，发现连接 u,v 一条边之后，相当于可以对 [u,v−1] 这段区间中的数进行循环移位，所以找到第一个不满足 ai=i 的和最后一个不满足 ai=i 的位置，将这段区间进行循环移位，判断能否合法即可。
-
剩下的答案为 2，这里给出一种构造：发现若能构造出能交换相邻两个数的操作，则整个序列一定可以任意排列。故连接 (1,n),(1,n−1)，设要交换 ai,ai+1，根据答案为 1 中的结论，总可以进行循环移位将这两位移到开头，所以不妨假设交换的相邻的两个数为 a1,a2，下文设 0 为空位，i 为初始位置 i 的数，当 n=4 时，可以进行如下操作：
12340→02341→23401→03421→13420→01342→21340
此时成功构造出来交换相邻两个数的操作，于是证明答案 ≤2。
时间复杂度 O(n)。
T3
先钦定节点 1 为根，即定根怎么做。
可以设计出来一个简单的 dp，dpi,j 表示以 i 为根的子树中有 j 个小型信标的方案数。
转移分为两种，一种为当前节点选择小型信标，即 dpi,1=1；另一种就是正常树上背包合并：设当前与儿子 v 合并，则有 dpi,k=∑j=0kdpi,j×dpv,k−j。初值有 dpi,0=1。滚动数组倒着枚举 k。
设 sizi 为以 i 为根的子树，不妨将上面的 dp 转移时间放大，即每次合并时间为 O(sizv×(n−sizv))，则总时间为 O(n×∑sizv−∑sizv2<n×∑sizv)，问题为求出 ∑sizv。考虑每个点都会造成自己祖先个数的贡献，所以总时间复杂度上限为 O(n2×d)。其中，d 为树高。由于保证数据随机，在这种随机生成树的情况下，树高期望为 logn，所以时间复杂度即为 n2logn。
对于每个根来说，dp 一次的时间复杂度是 O(n2×logn) 的，于是做到了 O(n3×logn)。发现对于相邻的根来说，很多节点的 dp 值都没有改变，所以考虑换根 dp。
假设当前根为 u，要将根换到 v 上，考虑处理三件事：
- 将 v 对 u 的贡献从 dpu 中退下。合并时是倒着枚举 k，退下贡献时则正着枚举 k。即 dpu,k=dpv,0dpu,k−∑j=0k−1dpu,j×dpv,k−j，由于 dpv,0=1，所以分母可以直接去掉，这样使用 O(n) 的时间就可以将 v 对 u 的贡献退下。
- 将 dpu 合并到 dpv 上，由于贡献已经退下，直接合并即可。
- 回溯是再将 dpu 复原，可以考虑先备份 dpu 数组。
换根的时间复杂度分析跟背包合并分析相同，总时间复杂度 O(n2×logn)。
T4
发现左端点一定为前缀 min，右端点一定为后缀 max。将这些端点进行重编号，考虑对中间的每个点 i 算贡献，其会对 l<i∧al<ai 的左端点和 r>i∧ar>ai 的右端点产生贡献。由于前缀 min 和后缀 max 都具有单调性，二分找出临界端点，相当于对 l∈[a,b]∧r∈[c,d] 的矩形加 1，最后查全局 max。扫描线加线段树维护即可。
有帮助，赞一个