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