2021集训队互测 Lovely Dogs

· · 个人记录

最近模拟赛做自闭了。

每天集训队互测的题目，一天比一天难，搞得改题都只能保一争二；今天也只改了这道题目，就写一下只关于这道题目的总结吧。

题目大意：

定义一个 f_z(x)= \prod[c_i \le k](-1)^{c_i},x=\prod(p_i^{c_i}) 。

对于每一颗子树，需要计算出 \sum_{x \in S} \sum_{y \in S} f_z(a_xa_y)，其中 S 表示这棵子树的点集。

应该首先考虑大方向，就是说我们对于一个集合 $S$ ，尝试快速插入与计算加入一个新的 ax 的方法，如果我们完成了这个，那么只需要套一个启发式合并，这题就做完了。 首先发现如果 $z$ 足够大（就是达不到），那么设 $g(x)= \prod(-1)^{c_i},x=\prod(p_i^{c_i}) $，容易发现这是一个完全积性函数。 考虑如何快速插入，发现这个 $z$ 的限制简直就太恶心了，于是我们考虑将$f_z$转化为$g$，使用容斥干掉他。 考虑枚举一个 $t = \prod p_i$，表示 $t$ 的质因子都是次数大于等于 $d+1$ 的。 那么此时计算的公式就可以写出来了（其中 $a$ 表示原来集合中的数，$v$表示新加入的）：

\sum_{i=1}^rf_z(a_iv)

\sumt \mu(t)\sum{i=1}^r[t^{d+1}|a_iv]g(a_iv)

\sumt \mu(t)\sum{i=1}^r[t^{d+1}|a_iv]g(a_i)g(v)

g(v) \sumt \mu(t)\sum{i=1}^r[\frac{t^{d+1}}{gcd(t^{d+1},v)}|a_i]g(a_i)

记 $C=\frac{t^{d+1}}{gcd(t^{d+1},v)}$。 那么就是：

g(v) \sumt \mu(t)\sum{i=1}^r[C|a_i]g(a_i)

那么计算就可以直接枚举 $t$ ，然后用一个桶记录 $\sum_{i=1}^r[C|a_i]g(a_i)$。 那么插入也就是枚举约数然后对应位置加上 $g(v)$。 比较难打，非常难调，貌似还有些卡常？~~然而我调完WA就过了，还是中间就要注意精细实现啊。~~