251104 模拟赛
T1
构造一组排列，每次可以沿着排列边或者逆排列的边走一步，使得从任意点开始都能走到任意点。\(ceil(log n)+1\)。
发现构造 \(\{1,2,4,8\cdots\}\) 可以通过 \(n\) 是奇数的测试点，这时因为上面的集合可以构造出任意偶数，在 \(n\) 为奇数时只需多绕一圈即可变成奇数。\(n\) 为偶数时我们需要想办法改变奇偶性。考虑 \(n=4\) 时转换奇偶性的构造：
把这个构造复制 \(\frac{n}{4}\) 份，就达到目的了。然而在 \(n\bmod 4=2\) 时不行，还需要多加一次处理最后两个数。发现这样做次数也是够的。
T2
给定长为 \(n\) 的序列 \(a\)，定义 \(f(x)=\max_{i}\max_{0\le t\le x}\{a_i\oplus t\}\)，\(g(x)\) 表示上式中取到最大值时 \(i\) 的种类数。给定 \(k\)，求 \(\sum_{x=0}^{2^k-1}f(x)\) 和 \(\sum_{x=0}^{2^k-1}g(x)\)。
首先注意到最大值一定由 \(a_i\) 的最大值贡献，因为固定一个 \(x\)，当前一位 \(a_i\) 取 \(1\) 总是不劣的。这里贡献可以简单 \(O(\log V)\) 求出。
考虑计数最大值个数。考虑一个 \(a_i\) 在 \(x\) 满足什么条件时成为最大值。总之最后是容易统计的。
T3
给定 \(n-1\) 次多项式 \(P\)，求 \(P^k\) 中有多少项的系数为奇数。
首先，如果已经钦定 \(P\) 中各项贡献的次数，那么贡献系数形如一个可重集排列。众所周知可重集排列数为奇数当且仅当 \(b_{0\sim n-1}\) 的二进制位对应的集合是总数 \(k\) 的一个集合划分。因此对 \(k\) 进行数位 dp，尝试记录进位信息，然后对本质不同的低位进行计数。发现这样做有问题，当低位相同但进位不同时可能最终转移到相同的状态，但没有进行抵消，从而算重。注意到固定一个低位，能生成的进位的集合是唯一的，因此 \(2^n\) 进行状压，预处理转移系数（枚举每个进位，再枚举分给哪个 \(a_i\)，再枚举即将被扔掉的第 \(i\) 位，进行抵消后转移到一个新集合），时间复杂度 \(O(2^n\log k+n^22^n)\)
T4
对一棵大小为 \(n\) 的带权无根树维护三种操作：
- 插入一个关键点 \((x,k)\)，覆盖 \(x\) 的 \(k\)-邻域内的所有点；
- 删除某个关键点；
- 查询 \(x,y\) 两点之间的路径上的所有点是否都被覆盖；
路径查询用动态树分治没有前途。考虑用树剖维护，插入时把根链跳一遍，查询时再把根链跳一遍。