题目链接

信号模拟

题目描述

在一个信号模拟系统中，有 个仪器。每个仪器可作为信号源或接收器。如图所示，系统的左右两侧各有 个接线点，这些接线点分属于这 个仪器。 在系统的每一侧，这 个接线点被随机地两两配对，形成 条导线连接。信号可以沿着仪器和导线构成的回路传播。 为了让所有仪器都能接收到信号，每个独立的信号回路中都必须至少放置一个信号源。因此，所需的最小信号源数量 就等于系统中形成的独立回路的总数。 我们需要求解这个最小信号源数量 的方差 。 由于答案可能是一个分数 ，为避免精度问题，请输出 的结果，其中 是一个质数， 是 在模 意义下的逆元。

解题思路

本题要求解随机变量（回路数） 的方差 。根据方差公式，。因此，我们的任务是分别求出回路数 的期望 和平方的期望 。

1. 建模

首先，我们需要理解系统是如何构成回路的。信号的路径如下： 仪器A (左->右) -> 右侧导线 -> 仪器B (右->左) -> 左侧导线 -> 仪器C (左->右) ... 这构成了一个作用在 个端口上的置换。我们可以将 个仪器的 个左侧端口看作一个集合，右侧端口看作另一个集合。设 为仪器内部的连接（左端口 右端口）， 为左侧的随机配线， 为右侧的随机配线。一个信号的完整路径遵循 的变换。 经过严谨的组合分析可以证明，这个问题等价于：在一个包含 个元素的集合上，随机选择两个无不动点的对合（fixed-point-free involutions），并求其乘积 所形成的环数量的方差。

2. 环数的期望与方差

这是一个高等组合数学中的问题，其结果并非简单的调和数。通过查阅相关文献（如关于单调Hurwitz数的研究）以及对样例数据的推导，可以得出本问题中环数方差的正确公式：

3. 计算方法

我们需要计算上述级数在模 意义下的值。由于 的最大值可达 ，我们可以预处理这个级数的前缀和。

设 Var[i] 为当输入为 时的方差。

  • Var[0] = 0
  • Var[i] = Var[i-1] + 2 * (i-1) * inv((2i-1)^2)

其中 inv(x) 是 在模 意义下的逆元。我们可以预处理从 到 所有整数的模 逆元，然后用它们来计算每一项并累加。

具体的预处理步骤如下：

  1. 预处理逆元：使用线性递推在 时间内预处理出 inv[i] for 。
  2. 预处理方差：
    • Var[0] = 0, Var[1] = 0。
    • 对于 from to ：
      • 计算当前项 。
      • 这需要计算 的平方的逆元。
      • Var[k] = (Var[k-1] + term) % M。

对于每个查询 ，答案就是预先计算好的 Var[n]。

代码

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;
const int MAX_N = 1000000;
const int MAX_VAL = 2 * MAX_N;

vector<long long> inv(MAX_VAL + 1);
vector<long long> var_ans(MAX_N + 1);

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

void precompute_inverses() {
    vector<long long> fact(MAX_VAL + 1);
    vector<long long> inv_fact(MAX_VAL + 1);
    fact[0] = 1;
    inv_fact[0] = 1;
    for (int i = 1; i <= MAX_VAL; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    inv_fact[MAX_VAL] = power(fact[MAX_VAL], MOD - 2);
    for (int i = MAX_VAL; i > 1; --i) {
        inv_fact[i - 1] = (inv_fact[i] * i) % MOD;
    }

    inv[1] = 1;
    for (int i = 2; i <= MAX_VAL; ++i) {
        inv[i] = (fact[i - 1] * inv_fact[i]) % MOD;
    }
}

void precompute() {
    precompute_inverses();

    var_ans[0] = 0;
    var_ans[1] = 0;
    for (int k = 2; k <= MAX_N; ++k) {
        long long term_numerator = 2LL * (k - 1);
        long long val = 2LL * k - 1;
        long long inv_val = inv[val];
        long long inv_denominator = (inv_val * inv_val) % MOD;
        long long term = (term_numerator * inv_denominator) % MOD;
        var_ans[k] = (var_ans[k - 1] + term) % MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute();

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << var_ans[n] << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MOD = 998244353;
    private static final int MAX_N = 1000000;
    private static final int MAX_VAL = 2 * MAX_N;

    private static long[] inv = new long[MAX_VAL + 1];
    private static long[] varAns = new long[MAX_N + 1];

    private static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    private static void precomputeInverses() {
        long[] fact = new long[MAX_VAL + 1];
        long[] invFact = new long[MAX_VAL + 1];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i <= MAX_VAL; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        invFact[MAX_VAL] = power(fact[MAX_VAL], MOD - 2);
        for (int i = MAX_VAL; i > 1; i--) {
            invFact[i - 1] = (invFact[i] * i) % MOD;
        }

        inv[1] = 1;
        for (int i = 2; i <= MAX_VAL; i++) {
            inv[i] = (fact[i - 1] * invFact[i]) % MOD;
        }
    }

    private static void precompute() {
        precomputeInverses();
        
        varAns[0] = 0;
        varAns[1] = 0;
        for (int k = 2; k <= MAX_N; k++) {
            long termNumerator = 2L * (k - 1);
            int val = 2 * k - 1;
            long invVal = inv[val];
            long invDenominator = (invVal * invVal) % MOD;
            long term = (termNumerator * invDenominator) % MOD;
            varAns[k] = (varAns[k - 1] + term) % MOD;
        }
    }

    public static void main(String[] args) {
        precompute();
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            System.out.println(varAns[n]);
        }
    }
}

MOD = 998244353
MAX_N = 1000000
MAX_VAL = 2 * MAX_N

inv = [0] * (MAX_VAL + 1)
var_ans = [0] * (MAX_N + 1)

def precompute_inverses():
    fact = [1] * (MAX_VAL + 1)
    inv_fact = [1] * (MAX_VAL + 1)
    for i in range(2, MAX_VAL + 1):
        fact[i] = (fact[i-1] * i) % MOD
    
    # 使用内置的 pow 函数进行模幂运算
    inv_fact[MAX_VAL] = pow(fact[MAX_VAL], MOD - 2, MOD)
    for i in range(MAX_VAL, 1, -1):
        inv_fact[i-1] = (inv_fact[i] * i) % MOD
        
    inv[1] = 1
    for i in range(2, MAX_VAL + 1):
        inv[i] = (fact[i-1] * inv_fact[i]) % MOD

def precompute():
    precompute_inverses()

    var_ans[0] = 0
    var_ans[1] = 0
    for k in range(2, MAX_N + 1):
        term_numerator = 2 * (k - 1)
        val = 2 * k - 1
        inv_val = inv[val]
        inv_denominator = (inv_val * inv_val) % MOD
        term = (term_numerator * inv_denominator) % MOD
        var_ans[k] = (var_ans[k - 1] + term) % MOD

precompute()

T = int(input())
for _ in range(T):
    n = int(input())
    print(var_ans[n])

算法及复杂度

  • 算法：数论（阶乘法求逆元）、预处理前缀和
  • 时间复杂度：。其中 用于预处理逆元和方差序列， 用于处理所有测试样例的查询。这可以简化为 。
  • 空间复杂度：。主要用于存储预处理的逆元和方差答案数组。