官方题解|偶数Ⅱ

我们定义 $f[j]$ 为对于所有 $i \in \{1 \sim j - 1\}$ ，第 $j$ 个奇数与第 $i$ 个奇数组合后所产生的贡献值。例如，$f[2] = 1$，这是因为第一个奇数是 $1$，第二个奇数是 $3$，两数相减为 $2$，$2$ 会产生一点贡献。依此类推。

方法一

接着，我们思考表达式 $\left | a - b \right |$
的本质，它实际上是在求数轴上两点之间的距离。那么，最终结果所产生的贡献值是否可以转化为到 $j$ 点距离为 $2$
的点的数量加上到 $j$ 点距离为 $4$ 的点的数量，以此类推。

由此，我们推测 $f[j + 1]$ 可以转化为 $j + \lfloor\frac{j}{2} \rfloor + \lfloor\frac{j}{4} \rfloor + \cdots$

进而得到 $f[j + 1] - f[\lfloor \frac{j}{2} + 1 \rfloor] = j$

基于此，我们可以通过线性动态规划来计算每一个 $f[j]$。

方法二

我们思考，表达式 $\left | a - b \right | =\left | a + 2 - b + 2 \right | $

那么对于每一个 $f[j - 1 ]$ 向 $f[j]$ 递推的时候。其实可以递推为 $f[j]=f[j-1] + \log(2 *j)$.

然后，结合前缀和以及相应的逆元操作，即可解决本题。

时间复杂度O（$n+ q$ ）

#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) {
    Comb::init(t + 10);
    ans.resize(t + 10);
    for (int i = 1; i <= t; i++) {
        ans[i + 1] = add(ans[i / 2 + 1], i);
    }
    for (int i = 1; i <= t; i++) {
        ans[i] = add(ans[i], ans[i - 1]);
    }
    for (i64 i = 3; i <= t; i++) {
        ans[i] = mul(ans[i], Comb::iC(i, 2));
    }
}


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