P3351.第3题-信号模拟
题目内容
如下图所示，有 2×n 个仪器，中间的方块是仪器的主体，每个仪器可以充当接收器或者信号源；主体的左右两侧是两个接线点。
现在，我们将左端 2×n 个接线点随机分成 n 组，每组各含两个点，并将右端 2×n 个接线点同样随机分成 n 组。然后将每组的两个接线点用导线连接。
这样一来，我们就得到了一组封闭的信号线路。具体而言：
这个过程持续进行，最终会形成若干个独立的循环。
现在，记 x 表示在所有接收器均能接收到信号的前提下， 2×n 个仪器中作为信号源的最少数量。求解 x 的方差。
可以证明答案可以表示为一个不可约分数 qp，为了避免精度问题，请直接输出整数 (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 需要使用公式 (qM−2 mod M) 得到。例如，计算 (45 mod M)：
(45modM)4−1
4−1=(4M−2 mod M)
=748683265
(45 mod M)=5×4−1 mod M
=5×748 683 265 mod M
=748 683 266
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T<104) 代表数据组数，每组测试数据描述如下：
在一行上输入一个整数 n(1≤n≤106) 代表仪器的数量。
输出描述
对于每组测试数据，新起一行输出一个整数，表示 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 个信号源的概率为 96 (如下左图所示，为其中一种情况)，需要 2 个信号源的概率为93 (如下右图所示，为其中一种情况)，故 :
- E(X)=1×32+2×31=34
- D(X)=E([X−E(X)]2)=(1−34)2×32+(2−34)2×31=92 。
我们能够找到， 887 328 314 ×9=7 985 954 826 对 M 取模后恰好等于分子 2，所以 887 328 314 是需要输出的答案。
