建模与关键观察

1）闭环 = 两个完美匹配的并

把每个仪器视为一个点：

• “左侧随机配对”在这些点上给出一个完美匹配 $\sigma$（若干 2-环）；
• “右侧随机配对”给出另一完美匹配 $\tau$。

把两种边（左/右）一起看，就是一个每点度为 2、边颜色交替的图，因此一定是若干个偶长环的并。每个环需要 1 个信号源，所以

$X=\text{环的个数}.$

等价地，固定其中一个匹配（例如把 $\sigma=(1\,2)(3\,4)\cdots(2n-1\,\,2n)$ 固定），只随机另一个匹配 $\tau$ 即可，分布不变。

2）逐步暴露（经典“开链闭合”过程）

从最小未访问的点出发，沿着“固定边 $\sigma$ 与当前已暴露的 $\tau$ 边”交替行走，会得到一条开链。当我们在这条链的“游离端”给它再连上一条新的 $\tau$ 边时：

• 共有 $2k-1$ 个可选端点（当前游离端除外已占去 $2k-2$ 个），

• 其中恰有 1 个会把开链闭成一个环，

• 因而第 $k$ 次尝试“闭合”的概率为

  $p_k=\frac{1}{2k-1}.$

把“在第 $k$ 次形成 $\tau$ 边时闭合一个环”的事件记为指示变量 $I_k$。整个构造会进行 $n$ 次，因此

$X=\sum_{k=1}^{n} I_k.$

进一步可以证明：这些 $I_k$ 彼此两两独立。理由：在第 $k$ 次时，游离端是均匀随机的，能闭合的那个端点在剩余的 $2k-1$ 个端点中是唯一且等可能的；第 $k$ 次是否闭合完全由本次选择决定，与之前是否闭合无关（之前只改变“剩余是谁”，不改变“唯一能闭合端点的相对概率”）。

期望与方差的封闭式

由线性期望：

由两两独立：

这正好与题面样例相符： $n=1$ 时 $E=1,\,D=0$； $n=2,3$ 时把上式转为模 $M$ 意义下的分数即可得到样例输出。

模运算与实现要点

• $M$ 为大质数，用费马小定理求逆元：$a^{-1}\equiv a^{M-2}\pmod M$。

• 

• 多组数据，建议先把所有 $n$ 的最大值记为 $N$，预处理：

  • 线性求逆（$O(N)$）得到 $1,2,\dots,2N-1$ 的逆元；
  • 仅对奇数做两条前缀和： $S_1[k]=\sum_{i=1}^{k}(2i-1)^{-1},\quad$ $S_2[k]=\sum_{i=1}^{k}(2i-1)^{-2}$。
  • 单次回答：$(S_1[n]-S_2[n])\bmod M$。

复杂度分析

• 预处理时间 $O(N)$，空间 $O(N)$；
• 单次询问 $O(1)$。 在约束 $T\le 10^4,\; n\le 10^6$ 下完全可行。

代码

Python

import sys
from array import array

MOD = 998244353

def read_ints():
    return list(map(int, sys.stdin.buffer.read().split()))

def solve():
    data = read_ints()
    it = iter(data)
    T = next(it)
    ns = [next(it) for _ in range(T)]
    N = max(ns)

    # 线性求逆：inv[i] = i^{-1} (mod MOD)，i=1..(2N-1)
    L = 2 * N - 1
    inv = array('i', [0]) * (L + 1)
    inv[1] = 1
    for i in range(2, L + 1):
        inv[i] = (MOD - (MOD // i) * inv[MOD % i] % MOD) % MOD

    # 只对奇数做前缀和
    S1 = [0] * (N + 1)  # sum 1/(2i-1)
    S2 = [0] * (N + 1)  # sum 1/(2i-1)^2
    for k in range(1, N + 1):
        j = 2 * k - 1
        x = inv[j]
        S1[k] = (S1[k - 1] + x) % MOD
        S2[k] = (S2[k - 1] + (x * x) % MOD) % MOD

    out = []
    for n in ns:
        ans = S1[n] - S2[n]
        if ans < 0:
            ans += MOD
        out.append(str(ans))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 998244353;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[] ns = new int[T];
        int N = 0;
        for (int i = 0; i < T; i++) {
            ns[i] = sc.nextInt();
            N = Math.max(N, ns[i]);
        }
        int L = 2 * N - 1;

        // 线性求逆 inv[i] = i^{-1} mod MOD
        int[] inv = new int[L + 1];
        inv[1] = 1;
        for (int i = 2; i <= L; i++) {
            long val = (MOD - (long)(MOD / i) * inv[MOD % i] % MOD) % MOD;
            inv[i] = (int) val;
        }

        // 前缀和（只对奇数）
        int[] s1 = new int[N + 1];
        int[] s2 = new int[N + 1];
        for (int k = 1; k <= N; k++) {
            int j = 2 * k - 1;
            long x = inv[j];
            s1[k] = (int) ((s1[k - 1] + x) % MOD);
            s2[k] = (int) ((s2[k - 1] + x * x) % MOD);
        }

        StringBuilder sb = new StringBuilder();
        for (int n : ns) {
            int ans = s1[n] - s2[n];
            if (ans < 0) ans += MOD;
            sb.append(ans).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
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(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if(!(cin >> T)) return 0;
    vector<int> ns(T);
    int N = 0;
    for(int i=0;i<T;i++){ cin >> ns[i]; N = max(N, ns[i]); }

    int L = 2*N - 1;

    // 线性求逆：inv[i] = i^{-1} (mod MOD)
    vector<int> inv(L+1);
    inv[1] = 1;
    for(int i=2;i<=L;i++){
        long long v = (MOD - 1LL*(MOD/i)*inv[MOD%i]%MOD) % MOD;
        inv[i] = (int)v;
    }

    // 只对奇数做前缀和
    vector<int> s1(N+1, 0), s2(N+1, 0);
    for(int k=1;k<=N;k++){
        int j = 2*k - 1;
        long long x = inv[j];
        s1[k] = addmod(s1[k-1], (int)x);
        s2[k] = addmod(s2[k-1], (int)(x*x%MOD));
    }

    for(int n: ns){
        int ans = submod(s1[n], s2[n]);
        cout << ans << '\n';
    }
    return 0;
}

题目内容

如下图所示，有 $2×n$ 个仪器，中间的方块是仪器的主体，每个仪器可以充当接收器或者信号源；主体的左右两侧是两个接线点。

现在，我们将左端 $2×n$ 个接线点随机分成 $n$ 组，每组各含两个点，并将右端 $2×n$ 个接线点同样随机分成 $n$ 组。然后将每组的两个接线点用导线连接。

这样一来，我们就得到了一组封闭的信号线路。具体而言：

• 信号从任一信号源 $i$ 出发，通过右侧接线点；

• 随后，信号通过与右侧接线点连接的导线到达另外一个仪器的左侧接线点，再经过仪器主体到达右侧接线点；此时，如果这个仪器是接收器，那么就视为接收到了信号(注意，接收到信号不会影响信号继续往后传递)。

这个过程持续进行，最终会形成若干个独立的循环。

现在，记 $x$ 表示在所有接收器均能接收到信号的前提下， $2×n$ 个仪器中作为信号源的最少数量。求解 $x$ 的方差。

可以证明答案可以表示为一个不可约分数 $\frac {p}{q}$，为了避免精度问题，请直接输出整数 $(p×q^{-1}$ $mod$ $M)$ 作为答案，其中 $M=998$ $244$ $353$ ，$q^{-1}$ 是满足 $q×q^{-1}≡1(mod$ $M)$ 的整数。更具体地，你需要找到一个整数 $x ∈ [0,M)$ 满足 $x × q$ 对 $M$ 取模等于 $p$ ，您可以查看样例解释得到更具体的说明。

【提示】 本题中，如果您需要使用到除法的取模，即计算 $(p×q^{-1}$ $mod$ $M)$时，$q^{-1}$ 需要使用公式 $(q^{M-2}$ $mod$ $M)$ 得到。例如，计算 $(\frac {5}{4}$ $mod$ $M)$：

$\frac {4^{-1}}{(\frac {5}{4} mod M) }$

$4^{-1}=(4^{M-2}$ $mod$ $M$) $=748683265$

$(\frac {5}{4}$ $mod$ $M)= 5×4^{-1}$ $mod$ $M$ $=5×748$ $683$ $265$ $mod$ $M$ $=748$ $683$ $266$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤ T < 10^4)$ 代表数据组数，每组测试数据描述如下：

在一行上输入一个整数 $n(1 ≤n≤ 10^6)$ 代表仪器的数量。

输出描述

对于每组测试数据，新起一行输出一个整数，表示 $x$ 的方差对 $M =998$ $244$ $353$ 取模后的结果。

样例1

输入

3
1
2
3

输出

0
887328314
168592380

说明

对于第一组测试数据，左、右两侧各仅有一种配对方式，构成一个长度为 $2$ 的循环。最小信号源数为 $1$ ，如下图所示。因此 $E(X)=1，D(X)=0$ 。

对于第二组测试数据，左侧有三种配对 ({$1,2$},{$3,4$};{$1,3$},{$2,4$};{$1,4$},{$2,3$})，右侧同样三种，合计 $3×3=9$ 种等可能组合。计算可得，需要 $1$ 个信号源的概率为 $\frac {6}{9}$ (如下左图所示，为其中一种情况)，需要 $2$ 个信号源的概率为$\frac {3}{9}$ (如下右图所示，为其中一种情况)，故 :

• $E(X)=1×\frac {2}{3}+2×\frac {1}{3}=\frac {4}{3}$
• $D(X)=E([X-E(X)]^2)=$$(1-\frac {4}{3})^2×\frac {2}{3}$$+(2-\frac {4}{3})^2$$×\frac {1}{3}$$=\frac {2}{9}$ 。

我们能够找到， $887$ $328$ $314$ $×9=7$ $985$ $954$ $826$ 对 $M$ 取模后恰好等于分子 $2$，所以 $887$ $328$ $314$ 是需要输出的答案。