2954. 感染序列的数目

Hard

题目描述

给定一个整数 n 和一个按递增顺序排列的数组 sick，表示一排 n 个人中感染者的位置。

在每一步中，与感染者相邻的一个未感染者会被感染。这个过程持续到所有人都被感染为止。

感染序列是未感染者被感染的顺序，不包括最初感染的人。

返回可能的不同感染序列数目，结果对 10^9 + 7 取模。

示例 1：

输入：n = 5, sick = [0,4]
输出：4
解释：
总共有 6 种不同的序列。
有效的感染序列是 [1,2,3]、[1,3,2]、[3,2,1] 和 [3,1,2]。
[2,3,1] 和 [2,1,3] 不是有效的感染序列，因为位置 2 的人不能在第一步被感染。

示例 2：

输入：n = 4, sick = [1]
输出：3
解释：
总共有 6 种不同的序列。
有效的感染序列是 [0,2,3]、[2,0,3] 和 [2,3,0]。
[3,2,0]、[3,0,2] 和 [0,3,2] 不是有效的感染序列，因为感染从位置 1 开始，然后是 2，再是 3，因此 3 不能比 2 更早被感染。

约束条件：

2 <= n <= 10^5
1 <= sick.length <= n - 1
0 <= sick[i] <= n - 1
sick 按递增顺序排列

解题思路

这是一道组合数学问题，需要分析感染传播的规律。

核心思路：

分段分析：将未感染的人群按位置分为若干连续段，每段被已感染者包围或位于边界。
段的分类：
- 边界段：位于数组开头或结尾，只有一侧有感染源，感染方向唯一
- 中间段：两侧都有感染源，每次可以选择从左边或右边感染
计算方法：
- 对于长度为 len 的中间段，有 2^(len-1) 种内部感染顺序
- 边界段只有 1 种感染顺序
- 所有段之间的感染顺序可以任意交错，这是一个多项式系数问题
公式推导：
- 设总的未感染人数为 S
- 中间段长度为 len[1], len[2], ..., len[m]
- 边界段长度为 len_start, len_end
- 答案 = S! / (len[1]! × len[2]! × ... × len_start! × len_end!) × 2^k
- 其中 k = (len[1]-1) + (len[2]-1) + ... + (len[m]-1)

实现要点：

预处理阶乘和逆元，支持高效的组合数计算
使用快速幂计算 2^k
注意模运算的处理

代码实现

class Solution {
public:
    static const int MOD = 1e9 + 7;
    
    long long power(long long a, long long b) {
        long long res = 1;
        while (b > 0) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    long long inverse(long long a) {
        return power(a, MOD - 2);
    }
    
    int numberOfSequence(int n, vector<int>& sick) {
        vector<long long> fact(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        
        vector<int> segments;
        int m = sick.size();
        
        // 处理第一个段（如果存在）
        if (sick[0] > 0) {
            segments.push_back(sick[0]);
        }
        
        // 处理中间段
        for (int i = 1; i < m; i++) {
            if (sick[i] - sick[i - 1] > 1) {
                segments.push_back(sick[i] - sick[i - 1] - 1);
            }
        }
        
        // 处理最后一个段（如果存在）
        if (sick[m - 1] < n - 1) {
            segments.push_back(n - 1 - sick[m - 1]);
        }
        
        int total = 0;
        for (int len : segments) {
            total += len;
        }
        
        if (total == 0) return 1;
        
        long long result = fact[total];
        int powerOf2 = 0;
        
        // 第一个段（边界段）
        int idx = 0;
        if (sick[0] > 0) {
            result = result * inverse(fact[segments[idx]]) % MOD;
            idx++;
        }
        
        // 中间段
        for (int i = 1; i < m; i++) {
            if (sick[i] - sick[i - 1] > 1) {
                int len = segments[idx];
                result = result * inverse(fact[len]) % MOD;
                powerOf2 += len - 1;
                idx++;
            }
        }
        
        // 最后一个段（边界段）
        if (sick[m - 1] < n - 1) {
            result = result * inverse(fact[segments[idx]]) % MOD;
        }
        
        result = result * power(2, powerOf2) % MOD;
        return result;
    }
};

class Solution:
    def numberOfSequence(self, n: int, sick: List[int]) -> int:
        MOD = 10**9 + 7
        
        def power(a, b):
            res = 1
            while b > 0:
                if b & 1:
                    res = res * a % MOD
                a = a * a % MOD
                b >>= 1
            return res
        
        def inverse(a):
            return power(a, MOD - 2)
        
        # 预计算阶乘
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i % MOD
        
        segments = []
        m = len(sick)
        
        # 处理第一个段
        if sick[0] > 0:
            segments.append(sick[0])
        
        # 处理中间段
        for i in range(1, m):
            if sick[i] - sick[i - 1] > 1:
                segments.append(sick[i] - sick[i - 1] - 1)
        
        # 处理最后一个段
        if sick[m - 1] < n - 1:
            segments.append(n - 1 - sick[m - 1])
        
        total = sum(segments)
        if total == 0:
            return 1
        
        result = fact[total]
        power_of_2 = 0
        
        # 第一个段（边界段）
        idx = 0
        if sick[0] > 0:
            result = result * inverse(fact[segments[idx]]) % MOD
            idx += 1
        
        # 中间段
        for i in range(1, m):
            if sick[i] - sick[i - 1] > 1:
                length = segments[idx]
                result = result * inverse(fact[length]) % MOD
                power_of_2 += length - 1
                idx += 1
        
        # 最后一个段（边界段）
        if sick[m - 1] < n - 1:
            result = result * inverse(fact[segments[idx]]) % MOD
        
        result = result * power(2, power_of_2) % MOD
        return result

public class Solution {
    private const int MOD = 1000000007;
    
    private long Power(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    private long Inverse(long a) {
        return Power(a, MOD - 2);
    }
    
    public int NumberOfSequence(int n, int[] sick) {
        long[] fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        
        List<int> segments = new List<int>();
        int m = sick.Length;
        
        if (sick[0] > 0) {
            segments.Add(sick[0]);
        }
        
        for (int i = 1; i < m; i++) {
            if (sick[i] - sick[i - 1] > 1) {
                segments.Add(sick[i] - sick[i - 1] - 1);
            }
        }
        
        if (sick[m - 1] < n - 1) {
            segments.Add(n - 1 - sick[m - 1]);
        }
        
        int total = segments.Sum();
        if (total == 0) return 1;
        
        long result = fact[total];
        int powerOf2 = 0;
        
        int idx = 0;
        if (sick[0] > 0) {
            result = result * Inverse(fact[segments[idx]]) % MOD;
            idx++;
        }
        
        for (int i = 1; i < m; i++) {
            if (sick[i] - sick[i - 1] > 1) {
                int length = segments[idx];
                result = result * Inverse(fact[length]) % MOD;
                powerOf2 += length - 1;
                idx++;
            }
        }
        
        if (sick[m - 1] < n - 1) {
            result = result * Inverse(fact[segments[idx]]) % MOD;
        }
        
        result = result * Power(2, powerOf2) % MOD;
        return (int)result;
    }
}

/**
 * @param {number} n
 * @param {number[]} sick
 * @return {number}
 */
var numberOfSequence = function(n, sick) {
    const MOD = 1000000007;
    
    // Precompute factorials and inverse factorials
    const fact = new Array(n + 1);
    fact[0] = 1;
    for (let i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    
    const invFact = new Array(n + 1);
    invFact[n] = modPow(fact[n], MOD - 2, MOD);
    for (let i = n - 1; i >= 0; i--) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
    
    function modPow(base, exp, mod) {
        let result = 1;
        while (exp > 0) {
            if (exp % 2 === 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp = Math.floor(exp / 2);
        }
        return result;
    }
    
    function comb(n, k) {
        if (k > n || k < 0) return 0;
        return (fact[n] * invFact[k] % MOD) * invFact[n - k] % MOD;
    }
    
    // Find segments of uninfected people
    const segments = [];
    
    // Left segment
    if (sick[0] > 0) {
        segments.push(sick[0]);
    }
    
    // Middle segments
    for (let i = 1; i < sick.length; i++) {
        const gap = sick[i] - sick[i - 1] - 1;
        if (gap > 0) {
            segments.push(gap);
        }
    }
    
    // Right segment
    if (sick[sick.length - 1] < n - 1) {
        segments.push(n - 1 - sick[sick.length - 1]);
    }
    
    if (segments.length === 0) return 1;
    
    const totalUninfected = segments.reduce((sum, seg) => sum + seg, 0);
    let result = fact[totalUninfected];
    
    for (let i = 0; i < segments.length; i++) {
        const segSize = segments[i];
        result = (result * invFact[segSize]) % MOD;
        
        // For middle segments, multiply by 2^(segSize-1) since they can spread in both directions
        if (i > 0 && i < segments.length - 1 && segSize > 0) {
            result = (result * modPow(2, segSize - 1, MOD)) % MOD;
        } else if (segments.length > 1 && ((i === 0 && sick[0] > 0) || (i === segments.length - 1 && sick[sick.length - 1] < n - 1)) && segSize > 0) {
            // Left and right segments when there are middle segments
            if (segments.length === 1) continue;
            // For edge segments when there are other segments, no additional factor needed
        }
    }
    
    // Recalculate more carefully
    result = 1;
    let remaining = totalUninfected;
    
    for (let i = 0; i < segments.length; i++) {
        const segSize = segments[i];
        if (segSize === 0) continue;
        
        result = (result * comb(remaining, segSize)) % MOD;
        remaining -= segSize;
        
        // For middle segments (not at boundaries), multiply by 2^(segSize-1)
        const isMiddleSegment = i > 0 && i < segments.length - 1;
        const isLeftEdge = i === 0 && sick[0] > 0;
        const isRightEdge = i === segments.length - 1 && sick[sick.length - 1] < n - 1;
        
        if (isMiddleSegment || (segments.length > 1 && (isLeftEdge || isRightEdge))) {
            if (isMiddleSegment && segSize > 1) {
                result = (result * modPow(2, segSize - 1, MOD)) % MOD;
            }
        }
    }
    
    // Recalculate with correct approach
    result = fact[totalUninfected];
    for (let seg of segments) {
        result = (result * invFact[seg]) % MOD;
    }
    
    // Apply the 2^(k-1) factor for middle segments
    for (let i = 1; i < segments.length - 1; i++) {
        if (segments[i] > 0) {
            result = (result * modPow(2, segments[i] - 1, MOD)) % MOD;
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(n + m log MOD)，其中 n 是总人数，m 是段数，阶乘预处理 O(n)，逆元计算 O(log MOD)
空间复杂度	O(n)，主要用于存储阶乘数组和段长度信息

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目