CF1408I

先计算出来全部 \(a_i\) 的异或和 \(X\)，减小若干 \(a_i\) 后再求异或和本质上是让 \(\rm X\) 异或上 \(a_i\oplus (a_i-d)\)

本题中的概率本质上是算序列数，所以设每个元素的 \(\rm EGF\) 为

其中 \(x\) 一维的指数运算是异或而 \(y\) 这维是加法，表示被操作的次数

如果可以求出来 \(\rm EGF\) 的乘积本题便迎刃而解了

考察本质不同 \(\rm K\) 元组 \(\{x\oplus (x-1),\dots x\oplus(x-K)\}\) 的数量级，取出后 \(\lceil\log_2K\rceil\) 位记作 \(t\)

如果 \(t>=K\) 这样的元素只会有 \(\Theta(K)\) 个，否则退位会影响到 \(c\) 个中的每一个，而每个退到的位都有 \(K\) 种可能，那么总数量级为 \(\Theta(cK)\)

此时得到的一种做法就是直接跑 \(\ln,\exp\) 来计算每种 \(\rm EGF\) 的快速幂，但是复杂度很高

尝试对于 \(\Theta(cK)\) 种 \(\rm EGF\) 固定 \(K+1\) 个中的一个 \(y^t\)，此时做 \(\rm FWT\) 前的序列只有一个位置有值，那么 \(\rm FWT\) 后每个 \(x\) 上的元素均为 \(\pm \cfrac{y^t}{t!}\) 中的一个

那么将 \(K+1\) 个 \(\pm 1\) 压下来做 \(\rm \ln,\exp\) 再快速幂即可通过

这种通过 转变考察维度 来减少运算量的技巧非常厉害！

CF1396E

拨开迷雾见月明

这个完美匹配是在诈骗，本质上是给树上的点两两配对，每对点的贡献是两者在树上的距离

既然是距离所以可以通过 \(d_x+d_y-2d_{\rm LCA(x,y)}\) 来统计，取出树的重心作为根，每次选择当前剩余点最多的两个子树中选出来一个点配对并删去

此时得到最大的距离和 \(\sum d_i\) ，同时不难找到最小的距离和：让每个点的儿子互相配对，如果有剩余则自己和其儿子配对，这时距离和为 \(\sum siz_i\bmod\ 2\)

后面构造的部分是平凡的

先判定 \(\rm K\) 不在值域内和 \(\rm K\)与最大值的差为奇数 的两个不合法情况，每次取出根的剩余点最多的一棵子树进行调整：

找到剩余点最多的子树并找到其最深的非叶子让它作为 \(\rm LCA\) 进行配对，如果其深度已经超过当前 \(\rm K\) 那么找到该点根链上深度为 \(K\) 的点让它和它儿子配对；没有超过就让该非叶子子树内配对并改变 \(\rm K\) 的数值

使用 std::set 维护重心所有儿子子树里面的点来实现上面的配对步骤，找剩余点最多的子树用优先队列，复杂度 \(\Theta(n\log n)\)