#P3351. 第3题-信号模拟
-
1000ms
Tried: 17
Accepted: 4
Difficulty: 8
所属公司 :
美团
时间 :2025年8月9日-开发岗
-
算法标签>数论
第3题-信号模拟
建模与关键观察
1)闭环 = 两个完美匹配的并
把每个仪器视为一个点:
- “左侧随机配对”在这些点上给出一个完美匹配 σ(若干 2-环);
- “右侧随机配对”给出另一完美匹配 τ。
把两种边(左/右)一起看,就是一个每点度为 2、边颜色交替的图,因此一定是若干个偶长环的并。每个环需要 1 个信号源,所以
X=环的个数.
等价地,固定其中一个匹配(例如把 σ=(12)(34)⋯(2n−12n) 固定),只随机另一个匹配 τ 即可,分布不变。
2)逐步暴露(经典“开链闭合”过程)
从最小未访问的点出发,沿着“固定边 σ 与当前已暴露的 τ 边”交替行走,会得到一条开链。当我们在这条链的“游离端”给它再连上一条新的 τ 边时:
-
共有 2k−1 个可选端点(当前游离端除外已占去 2k−2 个),
-
其中恰有 1 个会把开链闭成一个环,
-
因而第 k 次尝试“闭合”的概率为
pk=2k−11.
把“在第 k 次形成 τ 边时闭合一个环”的事件记为指示变量 Ik。整个构造会进行 n 次,因此
X=∑k=1nIk.
进一步可以证明:这些 Ik 彼此两两独立。理由:在第 k 次时,游离端是均匀随机的,能闭合的那个端点在剩余的 2k−1 个端点中是唯一且等可能的;第 k 次是否闭合完全由本次选择决定,与之前是否闭合无关(之前只改变“剩余是谁”,不改变“唯一能闭合端点的相对概率”)。
期望与方差的封闭式
由线性期望:

由两两独立:

这正好与题面样例相符: n=1 时 E=1,D=0; n=2,3 时把上式转为模 M 意义下的分数即可得到样例输出。
模运算与实现要点
-
M 为大质数,用费马小定理求逆元:a−1≡aM−2(modM)。
-

-
多组数据,建议先把所有 n 的最大值记为 N,预处理:
- 线性求逆(O(N))得到 1,2,…,2N−1 的逆元;
- 仅对奇数做两条前缀和: S1[k]=∑i=1k(2i−1)−1, S2[k]=∑i=1k(2i−1)−2。
- 单次回答:(S1[n]−S2[n])modM。
复杂度分析
- 预处理时间 O(N),空间 O(N);
- 单次询问 O(1)。 在约束 T≤104,n≤106 下完全可行。
代码
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 的方差。
可以证明答案可以表示为一个不可约分数 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 是需要输出的答案。
