题解

#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) {
Combinit(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], CombiC(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";
}
}