由于出题人和验题人姿势比较差，E题标解的思路比较繁琐且复杂度不够优秀，能处理的数据范围比较小，导致最终的结果是过了很多相对简单的低于的做法，导致这道题的实际难度低于预期。给各位大爷添堵了。感谢大爷们优秀做法，受教了。希望大家喜欢其它的题目。

A

将写为（为无平方因子数）的形式，则合法的解中，每个必然是的形式，且满足

问题等价于求上述方程的本质不同解数，可以DP解决。

B

将一个数字的位分成段，每段位，因为最多有位不同，故至少有一段完全相同，所以只需要枚举被询问数字的段，在与这个数字当前枚举到的段相同的数字中查询是否有解即可。因为数字随机，约有个数字，故每一块下期望检索到个数字，总复杂度为。

C

考虑两个串，，如果他们中的0的个数相同，那么可以从变到。

如何计算交换步数呢？考虑长度为的前缀，假设此时中的的个数为，中的个数为，且，则此时贡献了步。对每个前缀都计算出其贡献最后累加就得到了。

在这个算法上套一个数位DP即可，总复杂度可做到

D

对每个类型的基站维护一个set，存有哪些连续线段。再维护一个全局的set，存储三元组。每次覆盖操作时，在全局的set里找到相应线段，然后在对应类型基站的set中找相应线段，进行修改。这样，就可以保证全局set中的线段每次操作要么减少要么只会增加个。对于替换操作，作启发式合并即可。对于查询操作，二分即可。

E

这是出题人和验题人的原(la)始(ji)想法：由于修改一个节点会导致与之相连的所有的边发生改变，因此需要考虑修改不过于影响效率的做法。对于任何一条路径，无论修改哪个点，都最多影响该条路径上的两条边。因此可以考虑在欧拉序上进行带修改莫队。将每一条路径可以对应到欧拉序列上的一个区间，移动区间每移动一位需要计算一次边权。在按照时间修改时由于每次修改最多有两条边在当前路径上，可以记录下当前与每个点相连的边有哪几条对当前询问有贡献，因此一次修改最多需要计算两次边权。计算不超过 的边数使用树状数组维护一下即可。复杂度 。

F

化简

先把求和上下指标做一些处理

将拆一下

带回去得到结果

现在分别考虑每一项

引理 将集合映射到集合上。其中中的每个数字有恰好个原象。
证明 记。
首先显然能够看出，。
则，设，则有，其中为满足的任意整数解。
利用这种方法，对于任意满足的，都能分别构造出满足的。
因此，。

利用这个引理，可以将符号去掉。

拿出来前面一项

得

由于

所以结果为

和相同，因此对应项抵消。对于对称的两项同样抵消了。

结论

删掉抵消的以及和为0的项，所求的结果为

带入前面得到的结论，最终所求的和式就是

记为，记为，则上式可以写作

筛

综上，要筛这三个函数的前缀和

都是类似的。以为例，

然后要求的前缀和，由

得到

以此式子为基础进行杜教筛，加上预处理，可以的时间内筛出的前缀和。而在预处理之后也可以做到总复杂度。