T1

注意到步数限制很小所以直接双向广搜。倒着搜的时候要处理二次剩余，由于模数很小可以暴力，然后二次剩余只需要记一个，另一个就是模意义下取负，质数模数保证了一个数的二次剩余最多两个。双向各限制 \(8\) 步，正着搜最多扩展 \(4^8\) 个状态。倒着搜理论最多扩展 \(8^8\) 个状态（因为一个数的二次剩余可能有两个），但是一个数存在二次剩余的概率只有大概 \(\frac{1}{2}\)，又因为图是随机的，所以一个状态只有 \(\frac{1}{2}\) 的概率扩展，所以一个状态期望扩展的状态数也是 \(\frac{1}{2} \times 8 = 4\)，所以期望下倒着扩展状态数最多也是 \(4^8\)。因此总的复杂度为 \(O(p + 4^8)\)，随便写写就过了。

T2

首先发现只有二元组和三元组有用，因为多元组可以拆成若干二元组和至多一个三元组。

考虑二分答案。如果相邻两个数的差大于 \(mid\)，则选取的组不可能跨越这两个数的间隔，所以可以把大于 \(mid\) 的间隔断开，每个段分别考虑。可以证明，如果一个段内存在合法划分方案，那么一定存在一种合法方案最多包含一个三元组。先判段长度是不是偶数，如果是直接相邻的用二元组配对即可。如果是奇数就肯定要用三元组，先枚举三元组（由于合法三元组数量为 \(O(n^2)\)，所以总枚举量也不超过 \(O(n^2)\)），剩下的数根据结论如果存在合法方案就只需要用二元组。关于二元组配对最优方案肯定是从头开始相邻配对，证明用交换论证易证。如果二分值达到上界仍然无解输出 \(-1\)。时间复杂度 \(O(n^2 \log V)\)，其中 \(V\) 为值域。

T3

没有打表/手玩，很后面才发现结论。

首先可以发现只关心有多少个数以及每种数的出现次数，并不关心每种数具体的颜色。先观察一种局面。假设当前总共有 \(n\) 个数，每种数分别有 \(c_i\) 个，则按照题目所述二操作不能与之前有重复，在此限制下不同的变换结果即为多重集排列 \(\frac{n!}{\prod c_i !}\)。空局面先手必败。非空局面下，如果后续局面有一个先手必败的情况，则先手可以直接一步到达必败状态并切换先后手，因此此情况下先手必胜；如果后续局面全为先手必胜，则第一个删数的人必败。所以两个人都不想先删数，会不断重排序列。去除初始的排列方式，两人共可以操作序列 \(\frac{n!}{\prod c_i !} - 1\) 次，因此如果 \(2 \mid (\frac{n!}{\prod c_i !} - 1)\) 即 \(2 \nmid \frac{n!}{\prod c_i !}\)，则操作之后最初的先手还是先手，因此此情况下先手必败；否则操作之后可以切换先后手，此时先手必胜。

可以发现：无论什么情况，如果 \(2 \mid \frac{n!}{\prod c_i !}\)，则先手必胜；否则需要看后面的情况。因此输赢结论一定与 \(\frac{n!}{\prod c_i !}\) 的奇偶性密切相关。最终结论可以打表/手玩观察或归纳证明：当总数 \(n\) 为奇数时先手必胜；否则当 \(2 \mid \frac{n!}{\prod c_i !}\) 时先手必胜，否则后手必胜。

因此对于一个询问区间，先判断区间长度奇偶性，再判断多重集排列奇偶性。考虑怎么判断多重集排列奇偶性。可以把多重集排列转为组合数：\(\binom{n}{c_1} \binom {n-c_1}{c_2} \binom{n-c_1-c_2}{c_3} \cdots\)，只有所有组合数都是奇数最终结果才是奇数。因此只需要判断是否每一项模 \(2\) 都为 \(1\)。由组合数结论：\(2 \nmid \binom{n}{m} \iff m \subseteq n\)，因此需要满足每一项都有下是上的子集。发现如果要满足这个条件就要满足当前下是上的子集，然后用上剪掉下，再看后面的数是不是新的上的子集。在这种操作下，最多产生 \(popcount(n)\) 个组合数满足下是上的子集，因此如果当前区间的颜色种类数大于 \(popcount(len)\) 则多重集排列肯定是偶数，先手必胜。所以先判掉颜色数多的情况，颜色数不超过 \(popcount(len)\) 可以直接暴力，先把每种颜色取出来，再用 vector + 二分找到区间内每种颜色的出现次数，再扫一遍暴力判是否是子集即可。维护区间中的颜色种类数由于多于 \(21\) 个就直接不合法，因此只需要维护出现位置最晚的 \(21\) 个数。可以用栈暴力维护，栈底到栈顶位置递增，每次加入一个数如果有重复出现先把栈中的重复元素暴力删去，再把当前数压入栈顶，再看如果栈大小超过 \(21\) 直接把栈底扔了。这样可以在 \(O(\log n)\) 的时间内维护栈，然后把询问按右端点离线，先看区间长度奇偶性。然后查询区间内颜色数也可以暴力扫栈，如果超过 \(popcount(len)\)（最多 \(20\)）直接判先手胜，否则对于每种颜色计算出现次数再暴力判。这样的复杂度是 \(O(n \log^2 n)\) 的，瓶颈在于 \(O(n \log n)\) 次计算区间内某种颜色的出现次数。这个问题当然可以离线，转为前缀出现次数相减之后直接按右端点离线再开个桶即可。这样可以做 \(O(n \log n)\)，不过双 \(\log\) 常数比较小并且一般跑不满所以也可以比较快的通过。

总结：博弈题（特别是判断先后手胜负）先观察性质，如果观察性质后不太能直接得到一个简单的结论时可以考虑手玩/打表观察普遍规律，观察出来之后再可以尝试证明（一般是归纳证明，如果样本足够多的话也可以不证明）。

T4

Trie 除了描述树的结构以及子树内最大长度以外没有任何用。形式化题意为：给定一棵有根树，每个点 \(u\) 有两个权值 \(a_u,b_u\)，满足 \(a_{fa_u} \geq a_u\) 且 \(b_{fa_u} \geq b_u\)。对于一个点 \(x\)，称 \(y\) 合法当且仅当 \(dis(x,y) > a_y \land b_x \geq b_y\)。问对于每个 \(x\)，合法的 \(y\) 产生的连通块数量是多少。

首先有一个结论是如果 \(y\) 对于 \(x\) 合法那么 \(y\) 的任意一个后代 \(z\) 也合法。按照原题面的描述，\(x\) 自己的祖先链上的点肯定是不合法的。然后如果 \(y\) 合法，那对于 \(y\) 的后代来说，\(dis(x,z) > dis(x,y), a_z \leq a_y, b_z \leq b_y\)，因此 \(dis(x,z) > dis(x,y) > a_y \geq a_z \land b_x \geq b_y \geq b_z\)。因此得到结论：满足条件的点一定是一些子树。而要让一棵子树只统计一遍，可以考虑如下方案：给每个点 \(u\) 赋权为 \(c_u = 1 - son_u\)，其中 \(son_u\) 为 \(u\) 在原有根树上的儿子数量。这样一个子树就只会在子树根处统计到一个 \(1\) 的贡献，计数不重不漏。因此问题转为求满足上述限制的点的 \(c\) 之和。现在已不存在有根的限制，因此可以考虑点分治，将距离拆成两个点到分治中心的距离之和。这样问题就变成了点分治后二维数点，排序后树状数组，总时间复杂度为 \(O(n \log^2 n)\)，需要注意常数。

总结：如果要统计树上某些点组成的连通块数量，满足连通块肯定是一些子树构成，可以考虑赋权，每个点赋权为 \(1\) 减去自己在原树上的儿子数量。这样计算所有满足条件的点的点权和就只会在一棵子树的根处恰好贡献 \(1\)，因此计算正确。这是一个套路，要记住。