草稿

下文我们使用 \(\text{lowZ}\) 来表示美丽度， 即二进制表示后末尾连续 \(0\) 的个数。

首先这里存在一个不易观察到的结论：

在题目的要求下， \(f(a,b,c)\) 的答案， 即 \(\text{lowZ}(|a^c-b^c|)\)， 实际上等于 \(\text{lowZ}(|a-b|)\)。 关于这部分在末尾会给出初等证明。

因此题目要求的东西， 实际上和 \(c\) 是无关的， 我们只需要求若干个 \(\text{lowZ}(|a-b|)\) 就可以了。

题目中所说的前 \(n\) 个正奇数， 对应的就是 \(1,3,5,\cdots,2n-1\)。 任意奇数都可以表示成 \(2x-1\) 的形式， 我们取两个奇数 \(a\) 和 \(b\)， 分别表示为 \(a = 2i-1\) 和 \(b=2j-1\)。

显然 \(|a-b| = 2|i-j|\)， 我们尝试表示 \(\text{lowZ}(|a-b|)\)：

\[\begin{equation} \text{lowZ}(|a-b|) = \text{lowZ}(2|i-j|) = \text{lowZ}(|i-j|) + 1 \end{equation}\]

第二步转化是显然的， 一个数字乘以二等价于左移一位， 所以末尾会多一个 \(0\)。

那么我们记最后的答案为 \(ans\)，则有：

\[\begin{equation} ans = \sum_{a\neq b} \text{lowZ}(|a-b|) = \sum_{a\neq b} (\text{lowZ}(|i-j|) + 1) \end{equation}\]

我们可以发现 \(a\neq b\) 这个东西实际上是具有对称性的， 因此上面这个式子可以进一步化简成：

\[\begin{equation} n(n-1) + 2 \sum_{i>j} \text{lowZ} (i-j) \end{equation}\]

\(n(n-1)\) 是好算的，后面这一部分看起来并不好算， 我们只要想出来怎么计算后面这一式子就可以了。

我们思考一下， 对于若干个满足条件的 \((i,j)\) 实际上我们在求贡献的时候， 可以把其看做 \(t * 2^k\)， 其中 \(t\) 是一个奇数。 我们不妨尝试计算对于每一个 \(k\) 有多少满足条件的 \(t\)。

这里要记住，我们的 \(i\) 和 \(j\) 表达的实际上是我们对于前 \(n\) 个正整数编号之后， \(i\) 和 \(j\) 就表示了他们是这个正奇数数列中的第几项。

接下来这部分很重要：

我们枚举所有的 \(2^k\)，定义 \(m\) 为其最大序号差值，即 \(n-1\)。

这样一来我们可以使用 \(m\) 除以 \(2^k\)， 来表示 \(t * 2^k\) 中，我们最大可以取到的 \(t\)。

因为我们上面说了 \(t\) 一定是一个奇数， 我们定义 \(q = m / 2^k\) 所以这里我们可以使用 \(q - (q / 2)\) 来计算出 \(t\) 能取到多少个奇数， 我们记其为 \(cnt_k\)， 这个计算是平凡的，这里就不证明了。

之后我们记 \(s = (q + 1) / 2\)，这个的平方就是前 \(s\) 个奇数的和， 这个的证明也是平凡的，可以使用等差数列的求和公式。

于是我们可以用 \(2^k\) 乘以 \(s^2\) 来计算出所有 \(t * 2^k\) 的和。

对于每一个 \(t\)，它对应的 \(d = t * 2^k\) 在 \(1\leq t * 2^k \leq m\) 这个区间里出现的次数有 \(m+1-d\) 次， 其证明就是我们通过固定 \(d\)，则 \(i\) 一定在 \([1,m-d+1]\) 的区间里。

于是我们可以合理地计算出贡献了：

\[\begin{equation} 贡献 = k * \sum_t (m+1-d) = k * \sum_t (m+1-t*2^k) \end{equation}\]

我们对最右边的式子进行拆分求和，就变成：

\[\begin{equation} k * ((m+1)\times cnt_k - 2^k \times \sum_t t) \end{equation}\]

推到这个式子，已经就结束了，我们可以在 \(O(\log n)\) 的复杂度内求解单组解。

最后计算答案的时候，总三元组个数有 \(n(n-1)(n-2)\) 个， 所以我们有：

\[\begin{equation} \frac{n(n-1)+2\times sum}{n(n-1)(n-2)} = 1 + \frac{2\times sum}{n(n-1)} \end{equation}\]

最后给出文章一开始提到的结论的初等证明：

首先 \(a\) 与 \(b\) 是奇数， 因此 \(a-b\) 一定是一个偶数， 我们将其表示为 \(t * 2^k\)。

我们对 \(a^c-b^c\) 做一个分解：

\[\begin{equation} a^c - b^c = (a-b)\times (a^{c-1}+a^{c-2}b+\cdots +b^{c-1})。 \end{equation}\]

我们记其第二个因子为 \(C\)，因为 \(a\) 与 \(b\) 均为计数， 奇数的次幂一定是奇数，因此 \(C\) 中的每一项都是奇数， 共有奇数项，因此 \(C\) 一定是一个奇数。

于是我们就可以进行如下的拆解：

\[\begin{equation} |a^c - b^c| = |a-b| * C = t * 2^k * C \end{equation}\]

因为 \(t\) 与 \(C\) 为奇数是肯定的， 因此 \(\text{lowZ}\) 与且仅与 \(2^k\) 相关， 也就是与 \(C\) 无关，只和 \(|a-b|\) 相关。

文章开头的结论得证。

虽然这个题的 \(t\) 与 \(n\) 等阶，我这种做法和 \(O(n\log n)\) 预处理之后 \(O(1)\) 求解单组的时间复杂度一样， 但是单组 \(O(\log n)\) 可以求解更大的 \(n\)。