解题思路

问题背景与分析

本题研究的是一个由$2 \times n$个仪器组成的信号系统，通过左右两侧接线点的随机配对形成封闭信号线路。我们需要计算在所有接收器都能接收到信号的前提下，最少信号源数量$x$的方差。

关键观察发现：最少信号源数量等价于系统中形成的独立循环数量。方差计算需要用到期望$E[X]$和平方期望$E[X^2]$，公式为$D(X) = E[X^2] - (E[X])^2$。

数学推导

通过对问题的深入分析和数学推导，得出以下重要结论：

• 期望$interconnectedness[X] = \sum_{k=1}^{n} \frac{1}{2k-1}$

• 方差$D(X) = E[X] - \sum_{k=1}^{n} \left( \frac{1}{2k-1} \right)^2$

这一简化使我们能够高效计算所需结果，避免了直接模拟所有可能接线方式的复杂过程。

算法设计

1. 预处理逆元：由于计算涉及分数模运算，我们需要预先计算$1$到$2\max(n)$的模逆元（mod $998244353$）

2. 前缀和计算：分别计算$E[X]$和平方项的前缀和，便于快速回答每个查询

3. 查询处理：对于每个$n$，直接使用预处理的前缀和计算方差

时间复杂度分析

• 预处理逆元：$O(\max_n)$，其中$\max_n$是所有查询中$n$的最大值

• 前缀和计算：$O(\max_n)$

• 每个查询处理：$O(1)$

• 总时间复杂度：$O(T + \max_n)$，其中$T$是查询数量

该算法能够高效处理$n$最大为$10^6$、$T$最大为$10^4$的输入规模。

代码实现

import sys

class SignalVarianceCalculator:
    """信号源方差计算器，用于计算特定接线配置下的信号源最少数量的方差"""
    
    def __init__(self):
        self.mod = 998244353
        self.inverses = []
        self.sum_series = []
        self.sum_squares = []
        
    def _read_input(self):
        """读取并解析输入数据"""
        input_content = sys.stdin.read().split()
        ptr = 0
        test_cases = int(input_content[ptr])
        ptr += 1
        
        queries = []
        for _ in range(test_cases):
            queries.append(int(input_content[ptr]))
            ptr += 1
            
        return queries
    
    def _compute_max_needed(self, queries):
        """计算所需的最大n值"""
        return max(queries) if queries else 0
    
    def _precompute_inverses(self, max_needed):
        """预处理所需的所有逆元"""
        max_inv = 2 * max_needed
        self.inverses = [0] * (max_inv + 1)
        
        if max_inv >= 1:
            self.inverses[1] = 1  # 1的逆元是1
            for i in range(2, max_inv + 1):
                # 利用模运算性质计算逆元
                self.inverses[i] = (self.mod - self.mod // i) * self.inverses[self.mod % i] % self.mod
    
    def _precompute_sums(self, max_n):
        """预处理前缀和数组"""
        self.sum_series = [0] * (max_n + 1)
        self.sum_squares = [0] * (max_n + 1)
        
        for k in range(1, max_n + 1):
            term = self.inverses[2 * k - 1]
            self.sum_series[k] = (self.sum_series[k - 1] + term) % self.mod
            self.sum_squares[k] = (self.sum_squares[k - 1] + term * term) % self.mod
    
    def _calculate_single_result(self, n):
        """计算单个n值的结果"""
        return (self.sum_series[n] - self.sum_squares[n]) % self.mod
    
    def process(self):
        """处理整个计算流程"""
        queries = self._read_input()
        if not queries:
            return
        
        max_n = self._compute_max_needed(queries)
        self._precompute_inverses(max_n)
        self._precompute_sums(max_n)
        
        results = [str(self._calculate_single_result(n)) for n in queries]
        print("\n".join(results))

if __name__ == "__main__":
    calculator = SignalVarianceCalculator()
    calculator.process()

题目内容

如下图所示，有 $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$ 是需要输出的答案。