实际上就是做一个 进制异或卷积，那么转移矩阵就是范德蒙德矩阵（容易验证 ）。将 进行 之后得到的每一位都是 的形式。我们要做的，是加速求出 的每一位上，每种值分别用了多少次。我们用一个循环卷积来维护这个单位根，并求出 的 ，然后在每一位的多项式上就能看出每种 有多少种了。
事实上，我们将组合数 用 Lucas 定理展开后可以发现，这个组合数 当且仅当 在 进制下每一位都不进位！所以我们对于每个 ，向右暴力计算每个 的答案，遇到 就跳过（整段的对答案的贡献是一样的），遇到非 的元素，就遍历它非 的位进行计算，均摊一一下是 的。
用一个维护区间的平衡树维护每个循环的区间，然后就可以正常做了，均摊复杂度是对的，每次先 往左跑一下找到在哪个节点上，再向右 完成对后面的修正。
直接用线段树维护下区间和、区间前缀的连乘的积、后缀的连乘的积、中间的和，即可转移和维护区间覆盖为加法/乘法。难点在于，区间赋值为一个数怎么做？我们维护下所有本质不同的连乘长度，这个数组长度是小于等于 的；而区间赋值时只要遍历这个数组并快速幂即可计算出新的区间和。pushup 的复杂度为 ，而快速幂部分，如果按照顺序从小到大进行计算，每次计算 ，复杂度则为 。
开一个线段树，线段树的每个节点上要保存一个 的分段函数，即记下 表示输入至少要达到 才会在最后减去 。考虑在 build 的时候如何 Pushup，在左儿子的 数组上进行枚举，每一段 的可达区间是一个区间 ，那么它所能控制的区间其实应该是：，双指针一下在这个区间内的右儿子的 即可。。
附一个 jbc 树的牛逼做法：Orz zhy & jbc。
Min-max 容斥一下，然后就变成了计算到达一个 的最小时间花费的期望，设一个转移矩矩阵 表示在树上随机游走，但是走到 中之后就不出去了，则根据 的第 行中非 元素的和就能求出期望步数。还有一种办法是在树上 dp，但是自下而上求出 关于 的表达式（一定是一次函数），然后就能向上转移了，到根处就能直接求出 ，然后再往下递归一遍。
一个重要的想法是，无视猎人的死亡，每次依然还是等概率选择一个不管死没死的猎人开枪，那么我们要计算的便是第一个人一枪不挨的前提下，其它猎人都被干掉的概率，那么我们 Min-max 容斥干掉所有别的猎人需要几枪：
那么这个式子是一个只和 相关的等比数列求和。利用多项式 01 背包（）求出每个 的贡献系数即可。当然，也可以枚举 死亡时，至少有 集合内的人还没死去，这个可能更靠谱一点（逃
考虑经典的区间最大子段和的线段树，每个节点上维护 四个值，把这四个值看作是四个一次函数，对于每个点，再记一个 表示偏差量最小达到 就会发生“击败”操作（一条直线取代了另一条直线去作为 或者 或者 ）。每次修改的时候，暴力向下递归至所有会发生击败操作的节点上。EI 证明了这个击败操作的摊还复杂度是 的，而查询显然是 的。
直接序列分块，对每个块，维护一个 的表，存下每两种颜色的最近距离，并且存下每个颜色最靠左/右的距离，于是就可以 询问。而修改的时候，若 ， 为空则忽略， 为空则修改一下指针即可，都不为空则需要 的时间来减少一种颜色，但好在均摊意义下是正确的。对于散块，暴力重构那两种颜色对应的两行、两列即可。