统计感冒序列的数目

题目

2954. 统计感冒序列的数目

---

给你一个整数 n 和一个下标从 0 开始的整数数组 sick ，数组按 升序 排序。

有 n 位小朋友站成一排，按顺序编号为 0 到 n - 1 。数组 sick 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒，他会传染给下标为 i - 1 或者 i + 1 的小朋友，前提 是被传染的小朋友存在且还没有得感冒。每一秒中， 至多一位 还没感冒的小朋友会被传染。

经过有限的秒数后，队列中所有小朋友都会感冒。感冒序列 指的是 所有 一开始没有感冒的小朋友最后得感冒的顺序序列。请你返回所有感冒序列的数目。

由于答案可能很大，请你将答案对 10^9 + 7 取余后返回。

注意，感冒序列 不 包含一开始就得了感冒的小朋友的下标。

示例 1：

输入：n = 5, sick = [0,4]
输出：4
解释：一开始，下标为 1 ，2 和 3 的小朋友没有感冒。总共有 4 个可能的感冒序列：
- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着有感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 2 的小朋友被传染。
最后，下标为 3 的小朋友被传染，因为他挨着感冒的小朋友 2 和 4 ，感冒序列为 [1,2,3] 。
- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 3 的小朋友被传染。
最后，下标为 2 的小朋友被传染，因为他挨着感冒的小朋友 1 和 3 ，感冒序列为  [1,3,2] 。
- 感冒序列 [3,1,2] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。
- 感冒序列 [3,2,1] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。

示例 2：

输入：n = 4, sick = [1]
输出：3
解释：一开始，下标为 0 ，2 和 3 的小朋友没有感冒。总共有 3 个可能的感冒序列：
- 感冒序列 [0,2,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。
- 感冒序列 [2,0,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。
- 感冒序列 [2,3,0] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。

提示：

• 2 <= n <= 10^5
• 1 <= sick.length <= n - 1
• 0 <= sick[i] <= n - 1
• sick 按升序排列。

题解

方法一：

思路

任意相邻的$sick_i$和$sick_{i+1}$，期间包含$sick_{i+1}-sick_{i}-1$个未感冒的人。他们感冒的序列有$2^{sick_{i+1}-sick_{i}-2}$种，每次有两种选择：左侧或右侧。而最后剩余的一个人是固定的选择。

$sick_0$左侧有$sick_0$个未感冒的人，只有一种感冒序列。

$sick_{n-1}$左侧有$n-1-sick_{n-1}$个未感冒的人，只有一种感冒序列。

考虑将这些感冒序列组合起来。每个感冒序列内部的相对位置不会变化，所以可以考虑在剩余的空位中选择若干个空位放置一个感冒序列。

现在存在$t$个空位，假设有三个感冒序列，长度分别为$a,b,c$

$t$个位置中选择$a$个放置第一个序列，共$\binom{t}{a}$种。

剩余$t-a$个位置选择$b$个放置第二个序列，共$\binom{t-a}{b}$种方法。

剩余$t-a-b$个位置选择$c$个放置第三个序列，共$\binom{t-a-b}{c}$种方法。

代码

class Solution {
public:
    using ll = long long;
    const ll MOD = 1e9+7;
    int numberOfSequence(int n, vector<int>& sick) {
        int sz = sick.size();
        int N = n+5;
        ll fac[N], inv_fac[N];
        auto fpow = [](ll x, ll p, ll m) {
            ll rt = 1;
            while (p) {
                if (p&1) rt *= x, rt %= m;
                x *= x; x %= m;
                p >>= 1;
            }
            return rt;
        };
        auto pre = [&]() {
            fac[0] = 1;
            for (int i=1; i<N; i++) {
                fac[i] = fac[i-1]*i%MOD;
            }
            inv_fac[N-1] = fpow(fac[N-1], MOD-2, MOD);
            for (int i=N-2; i>=0; i--) {
                inv_fac[i] = inv_fac[i+1]*(i+1)%MOD;
            }
        };
        pre();
        auto comb = [&](int n, int m) {
            return fac[n]*inv_fac[m]%MOD*inv_fac[n-m]%MOD;
        };
        ll ans = 1, a = n-sz;
        for (int i=1; i<sz; i++) {
            if (sick[i] == sick[i-1]+1) continue;
            ll c = sick[i]-sick[i-1]-1;
            ans *= fpow(2, c-1, MOD)*comb(a, c)%MOD;
            a-=c;
            ans %= MOD;
        }
        int l = sick[0], r = n-1-sick.back();
        // ans *= comb(a, l);
        // ans %= MOD;
        // ans *= comb(a-l, r);
        // ans %= MOD;
        ans *= comb(a, l+r);
        ans %= MOD;
        ans *= comb(l+r, r);
        ans %= MOD;
        return ans;
    }
};