官方题解|偶数Ⅰ

数学，枚举

首先，观察方程 $f(a,b,c)=\left | a^c - b^c \right |$ 。通过对该式子进行因式分解（例如，当 $c$ 为正奇数时，根据公式 $x^c - y^c = (x - y)(x^{c - 1} + x^{c - 2}y + \cdots + xy^{c - 2} + y^{c - 1})$ ），我们不难发现，在研究该方程的某些性质时，$c$ 的具体取值并不会对问题的本质产生实质性的影响。也就是说，在当前的问题背景下，$c$ 这一变量是冗余的。因为 $a - b$ 是偶数 ，后面的表达式是奇数。那么最终表达式的结果的末尾的二进制零的个数其实等于 $a-b$ 的末尾的二进制数零的个数。

基于上述分析，我们可以将原问题进行转化，即通过枚举变量 $a$ 和 $b$ 的取值，来计算式子 $\left | a - b \right |$ 的贡献值。

对于这个方法，在线是比较困难的，我们考虑离线先计算完每一个的结果。然后对每一次询问之间查表。

时间复杂度 O($n^2$)

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

namespace myMath {
    i64 mod = 998244353;

    i64 add(i64 x, i64 y) {
        x += y;
        if (x > mod) x -= mod;
        return x;
    }

    i64 sub(i64 x, i64 y) {
        x -= y;
        if (x < 0)x += mod;
        return x;
    }

    i64 mul(i64 x, i64 y) {
        x *= y;
        x -= x / mod * mod;
        return x;
    }

    i64 qpow(i64 x, i64 y) {
        i64 res = 1;
        while (y) {
            if (y & 1) res = mul(res, x);
            y >>= 1;
            x = mul(x, x);
        }
        return res;
    }

    i64 inv(i64 x) {
        return qpow(x, mod - 2);
    }

    i64 qdiv(i64 x, i64 y) {
        return mul(x, inv(y));
    }

    void set_mod(i64 x) {
        mod = x;
    }

    namespace Comb {
        int n;
        vector<i64> fa;
        vector<i64> ifa;
         void init(int _n) {
            n = _n;
            fa.assign(n + 1, 1), ifa.assign(n + 1, 1);
            for (int i = 1; i <= n; i++) fa[i] = mul(fa[i - 1], i);
            ifa[n] = inv(fa[n]);
            for (i64 i = n - 1; i; i--) {
                ifa[i] = mul(ifa[i + 1], i + 1);
            }
        }

        i64 C(int i, int j) {
            return mul(fa[i], mul(ifa[j], ifa[i - j]));
        }

        i64 iC(int i, int j) {
            return mul(ifa[i], mul(fa[j], fa[i - j]));
        }
    }

    //线性求逆元

    vector<i64> get_inv(int k) {
        vector<i64> in(k + 1, 1);
        for (int i = 2; i <= k; i++) {
            in[i] = mul(in[mod % i], sub(mod, mod / i));
        }
        return in;
    }
}

using namespace myMath;

vector<i64> ans;


void init(int t) {
    ans.resize(t + 1);
    for (int i = 2; i <= t; i++) {
        ans[i] = add(ans[i - 1], ans[i]);
        for (int j = 1; j < i; j++) {
            i64 z = 2 * i - 2 * j;
            ans[i] = add(ans[i], log2(z & -z));
        }
    }
    for (int i = 2; i <= t; i++) {
        ans[i] = qdiv(ans[i], (i) * (i - 1) / 2);
    }
}


int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    init(1e3 + 100);
    int t = 0;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }
}