题解 | 信号模拟

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

static const int MOD = 998244353;

int addmod(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}
int submod(int a, int b) {
    a -= b;
    if (a < 0)  a += MOD;
    return a;
}

int main() {
    int T;
    cin >> T;
    vector<int> ns(T);
    int maxn = 0;
    for (int i = 0; i < T; ++i) {
        cin >> ns[i];
        maxn = max(maxn, ns[i]);
    }
    // 需要到 2*maxn 的逆元（因为用到 1,3,5,...,2n-1）
    int LIM = 2 * maxn;
    vector<int> inv(LIM + 1, 0);
    inv[1] = 1;
    for (int i = 2; i <= LIM; ++i) {
        inv[i] = 1LL * (MOD - MOD / i) * inv[MOD % i] % MOD;
    }

    // 前缀和：S1[n] = sum_{k=1..n} 1/(2k-1)
    //         S2[n] = sum_{k=1..n} 1/(2k-1)^2
    vector<int> S1(maxn + 1, 0), S2(maxn + 1, 0);
    for (int k = 1; k <= maxn; ++k) {
        int odd = 2 * k - 1;
        int inv_odd = inv[odd];
        int inv2_odd = 1LL * inv_odd * inv_odd % MOD;
        S1[k] = addmod(S1[k - 1], inv_odd);
        S2[k] = addmod(S2[k - 1], inv2_odd);
    }

    for (int i = 0; i < T; ++i) {
        int n = ns[i];
        int ans = submod(S1[n], S2[n]); // Var = sum 1/(2k-1) - sum 1/(2k-1)^2
        cout << ans << '\n';
    }
    return 0;
}