牛客挑战赛62题解

A.，当且仅当两个数二进制下最高位是同一位。按照最高位分类统计即可。

B. 对于每个循环节分别处理。考虑中的一个循环节，则必须在中所处的循环节内。令与在中的同一个循环节内，且从出发，走步可以抵达，则对于中的同一个循环节的不同数字，对应的必须相同。假设此时该循环节长度为，则必须满足。最后用中国剩余定理判定同余方程组是否有解。

一组同余方程有解的充要条件是两两方程构成的方程组有解，显然方程的数目不超过个，暴力枚举每一对检查即可。

C.
显然的结论：最优的合成路线一定是从等级开始，不断合成高等级的物品直到无法合成，然后对高等级的物品重复同一过程。

令表示执行到 等级为的物品这一步 的时候，拥有个物品的情况下，最后能成功达成目标的概率。由高向低递推

通过DP转移：令表示当前情况下，拥有个等级物品，个等级物品（被合成的，不包括原有的）最后能成功达到目标的概率。令原有个等级的物品
边界：
转移
最后
时间复杂度，为物品数目

D.考虑先计算，然后换根dp。令为一个点所有连接它的边的边权和。那么假设当前根为,对应，将根移动到子节点,对应，两者之间的边权为。则对于子树内的叶子节点，概率乘以，对于子树外的叶子节点，概率乘以。这两部分操作均可以对叶子节点按dfs排序后化为区间乘法操作。

验题人和考场上的绝大部分选手都是将操作转化成了某种意义上的差分？然后通过一遍dfs处理出全部的答案。时间复杂度。然而出题人并不是这么做的

现在考虑这么一个问题。有一个序列和序列，支持两种操作：对序列进行区间乘法，将序列整体加到序列上。最后询问整个序列。不难发现这就是我们需要支持的操作。吉司机线段树（segment tree beats）可能可以解决这个问题，但我不会。不过的范围看起来就是可以萌萌哒分块做的。对序列进行分块，标记每一块序列需要乘以几，和序列上需要加上几倍的。每次对于端点的块，清空所有标记并下放答案，对于中间的块，对、序列分别打上标记。总复杂度。实际上叶子节点的数目会比小不少，常数上还有很大的余裕。（可能对出题人来说这个想法自然一点点）

E.同样的，验题人和考场上绝大部分选手采用了复杂度为左右的DP，现在介绍一下多项式做法。

首先，假设一个随从死了之后我们还能攻击它，不难发现这一点不影响答案，因为概率和攻击次数是无关的，唯一需要注意的是攻击已经死去的，攻击力为的随从不会增加你的随从数目，因为视为无效操作。
接下来，我们可以把每次攻击的随从编号写成一个序列，一个长度为的序列对概率的贡献是。考虑这个序列的生成函数。由于有两个信息要记录（是否对你的随从数目产生贡献，攻击了哪个随从），可以使用二维生成函数（也可以理解成一维的EGF，另一维背包转化成了OGF）。令代表对随从数目的贡献那一维，代表攻击随从编号那一维。则一个的随从对应的生成函数是，一个的随从对应的函数是。前面的代表没有被杀死的情况，后者代表了被杀死的情况。最后把所有的生成函数乘起来，对每一项计算贡献即可。

上面的做法有个问题，我们需要钦定某一个随从为序列的最后一位（因为事实上，我们攻击某个随从后，随从上限满了，就停止攻击。如果不钦定最后一位的话，所得到的序列可能是最后若干位对随从上限的贡献均为的序列，这显然不合法）。一个简单的做法是枚举那个随从，然后让对应的减一，并使得一个长度为的序列的贡献为。

有一个问题是存在项，这可以看成是第三维，并使用三维FFT。另一个解决方案是暴力背包计算这一维（因为很小），然后使用二维的FFT。
总复杂度应该是的，常数较大。

F.建图。每个小球对应一个点，每个容器对应个点。蓝球和红球之间连一条权值为的边。对于每个容器，将个点连成一条链，边权为.最后对于每条规定，将小球对应的点和容器对应的所有个点连边，边权为 。如果这张图中存在一个完美匹配，则有解；完美匹配中权值最大的那一个则对应着最小的代价。

如此，可以保证有尽量少的球不被放入（代价为）。对于每个容器，除去放入的时候连接的若干个点，剩下的点若为偶数个，也必然能两两相互匹配。

一个问题是：通常我们解决的都是一般图最大权匹配而不要求其为完美匹配，一种解决方案是将所有边的边权都加上一个极大的数，此时最大权匹配必定对应着最大匹配，即可检查它是否为完美匹配。

PS:在第一位选手用网络流的错误做法水过了之后我们就更改了数据，不幸的是由于一些技术原因，并没有实时同步到比赛上，直到第二位选手用错误做法水过我们才意识到，并紧急修了锅。好在这两位选手的最终rank都不会对比赛结果造成太大的影响，根据惯例并不对这两份代码rejudge；其余选手做法都是正确的。