单组O(logn)解法

下文我们使用 $\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$。

#define int long long
int fastPow(int a,int n) {
    int ans = 1; a %= MOD;
    while (n) {
        if (n & 1) ans = (ans * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return ans;
}
void NeverSayNever() {
    int n; cin >> n;
    int m = n - 1;
    int sum = 0;
    for (int k = 1;; ++k) {
        int kpow2 = 1LL << k;
        if (kpow2 > m) break;
        int q = m / kpow2;
        if (q == 0) break;
        int cntK = q - (q / 2);
        int s = (q + 1) / 2;
        sum += k * (cntK * (m + 1) - kpow2 * s * s);
    }
    int inv = fastPow(n * (n - 1) % MOD, MOD - 2);
    int res = (1 + (((2 * (sum % MOD)) % MOD) * inv) % MOD) % MOD;
    cout << res << endl;
}