CF1261F Xor-Set
我们把 \(A,B\) 集合分别处理，把其拥有的区间放到字典树上，就会拆成 \(O(n\log V)\) 个区间。
考虑其两两组合，每个区间都是形如前面若干位确定，后面 \(x\) 位任意。
两个区间组合，就是取 \(x\) 更大的那个后面都是任意的，前面的若干位合并起来即可。
但是这样就会有 \(O(n^2\log^2V)\) 个区间，我们还需要排序后去重略显困难。考虑减少无用的区间。
钦定 \(q_a\ge q_b\)，合并 \([p_a,p_a+2^{q_a})\) 与 \([p_b,p_b+2^{q_b})\) 时，我们接下来还要合并 \([p_b+2^{q_b},p_b+2^{q_b}+2^{q_{b_2}})\)。
上面 \([p_b,p_b+2^{q_b})\) 到 \([p_b+2^{q_b},p_b+2^{q_b}+2^{q_{b_2}})\) 的过程分两段，一段 \(q_b\) 递增，一段递减，段中不进位。
因为段中不进位（段间进位），前 \(q_a\) 位都不变，所以只有 \(q=0\) 或 \(q=q_a\) 的时候有用。
那么区间的数量只有 \(O(n^2\log V)\) 了。
AGC009E Eternal Average
将求平均数的过程看做是一个每个节点儿子数都是 \(k\) 的树，第 \(d\) 层的所有数的贡献是 \(k^{-d}\)。
考虑 \(0,1\) 的深度序列 \(\{x_i\},\{y_i\}\)，长度分别为 \(n,m\)。其合法的话就是要其能对应到一棵树上。
将 \(0\) 看做 \(1\)，条件很明显也就是只需要满足 \(\sum k^{-x_i}+\sum k^{-y_i}=1\) 即可。
我们也就是要求的是：所有合法 \(x,y\) 序列中 \(\sum k^{-x_i}\) 有多少种，我们不难想到把这个东西写成 \(k\) 进制。
相当于直接 dp 答案的值，也就是说求序列 \(\{z_i\}\) 的个数，使得 \(\sum k^{-x_i}=\sum z_ik^{-i}\)。
假设已知 \(\{z_i\}\)，我们要看能否构造出长度为 \(n\) 的序列 \(\{x_i\}\)。
不妨先令 \(x\) 中 \(i\) 的出现次数为 \(z_i\)，\(\sum z_i\) 与 \(n\) 的差值可以用下放一位来补齐，每次可以增加 \(k-1\)。
所以 \(\{z_i\}\) 合法的条件是 \(\sum z_i=n\pmod {k-1}\)，且 \(\sum z_i \le n\)。
我们还需要考虑 \(1-\sum z_ik^{-i}\) 能构造出长度为 \(m\) 的序列 \(\{y_i\}\)。
也就是 \(1+\sum (k-z_i-1)\le m,1+\sum (k-z_i-1)=m\pmod{k-1}\)。后者跟上面那个同余式等价。
还有一个条件就是 \(z\) 序列长度为 \(l\)，\(z_i\in [0,k),z_{l}\neq 0\)。这个可以用 dp 求出答案。
设 \(f_{i,j}\) 表示当前填到前 \(i\) 位，\(\sum z_i=j\) 的方案数。考虑前缀和优化即可。