题解

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int MAX_K = 6000;
vector<int> v2(MAX_K + 1, 0);
vector<long long> pre_sum_v2(MAX_K + 1, 0);
vector<long long> pre_sum_dv2(MAX_K + 1, 0);
void precompute() {
for (int d = 1; d <= MAX_K; d++) {
int x = d;
while (x % 2 == 0) {
v2[d];
x /= 2;
}
}
for (int d = 1; d <= MAX_K; d) {
pre_sum_v2[d] = pre_sum_v2[d - 1] + v2[d];
pre_sum_dv2[d] = pre_sum_dv2[d - 1] + 1LL * d * v2[d];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
precompute();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int c1 = (n + 1) / 2;
int c3 = n / 2;
auto calc_case1 = [&](int m) -> long long {
if (m <= 1) return 0;
long long part1 = 2LL * m * (m - 1);
long long part2 = 2 * (m * pre_sum_v2[m - 1] - pre_sum_dv2[m - 1]);
return part1 + part2;
};
long long sum_case1 = calc_case1(c1) + calc_case1(c3);
long long sum_case2 = 2LL * c1 * c3;
long long total = (sum_case1 + sum_case2) % MOD;
long long denominator = 1LL * n * (n - 1) % MOD;
auto mod_pow = [&](long long a, int b) {
long long res = 1;
a %= MOD;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
};
long long inv_denominator = mod_pow(denominator, MOD - 2);
long long ans = total * inv_denominator % MOD;
cout << ans << '\n';
}
return 0;
}