CF1770

vp。

A. Koxia and Whiteboards

无脑换最小的一定最优。用小根堆或者 multiset 维护。

B. Koxia and Permutation

构造排列 。容易发现无论 为何值这样都是最优的。

C. Koxia and Number Theory

有相同的数显然不行。

合法的充要条件：对于每个素数 ，若存在 ，则有 。

也就是说，若原数组中的所有数对 取模后每种余数都出现了至少 次则无解，否则有解。

D. Koxia and Game

先尝试判定确定的局面。

结论：若先手必胜，则先手移除一个数后，后手得到的两个数必定相等。且这些数一定构成了 的排列。

否则后手必定能使其无法得到排列。

那么，原问题转化为：序列 的第 位可以取 或 ，求可以形成多少种不同的排列。

进一步转化。在 与 间连边，求有多少种给边定向的方式使得每个点入度均为 。

显然只有每个连通块构成基环树才有解。基环树定向方式只有环上两种。

需要注意的是，带自环的基环树贡献为 。

E. Koxia and Tree

先把随机取两点转换为距离和除以 。

考虑经典静态问题。

不妨设边 连接 两点，。记 表示 子树内关键点数量。

答案即为 。

现在关键点会跑了，怎么办？

由于每条边至多只会被一个关键点经过，因此任何情况下的真实 至多与静态下相差 。

可以维护每一个点是关键点的概率 ，修改到第 条边时计算贡献，然后 。

F. Koxia and Sequence

神仙题。

记 表示 时合法序列的方案数。

这个序列更像是可重集，。因此， 为偶数时答案为 。

由于异或的性质，只需要计算 意义下的答案。

把拆贡献进行到底，重新设 表示二进制下第 位为 的贡献。

按位或结果恰好等于 很难统计，记 表示或和为 的子集时的贡献。简单容斥可得答案为 。

根据 定理的推论或 时的 定理， 是 的子集 。

于是可以列出柿子 。

然后就不会了。