3130. 找出所有稳定的二进制数组 II

Mar 10, 2026

1250 字约 7 分钟

思路分析

流程概述

这是3129的强化版，题面没有区别，区别在于数据范围由 $200$ 到了 $1000$ ，这就说明我们不能再使用 $O(N^2)$ 的 $dp$ 了。

重新考虑题目，等价于 $arr$ 数组内连续的 $0$ 或 $1$ 的个数不能超过 $limit$

则问题转化为，将 $zero$ 个 $0$ 分成 $i$ 组，其中每组的个数至少 $1$ 个且不超过 $limit$ ，同理也将 $one$ 个 $1$ 分成 $j$ 组。

假设当前我们已经分组完毕，现在问题就是怎么将这些 $0,1$ 的组排列在一起，从而让它们连续都不超过 $limit$ ，显然只有四种情况可以做到：

$1. \, 010101...01(i=j)$

$2. \, 101010...10(i=j)$

$3. \, 010101...010(i=j+1)$

$4. \, 101010...101(j=i+1)$

其他情况都会导致存在两个 $0$ 或 $1$ 组连在一起，从而可能超过 $limit$ 的限制。

那么现在我们只需要遍历所有可能的组数 $i$ 和 $j$ ，然后将这些合法的方案数加在一起就得到答案。

其中 $i \in [1,zero],j \in [1,one]$ ，且当且仅当 $|i-j| \le 1$ 时，这组答案有效。

则我们只需要遍历到 $min(zero,one)$ 就可以，将时间复杂度优化到了 $O(N)$ 级别。

那么问题来了，怎么计算将 $0$ 和 $1$ 分成合法分组的方案数？我们使用组合数学的知识来求解。

单色分组

我们定义一个函数 $f(n,k,limit)$ 表示将 $n$ 个元素分成 $k$ 组且每组个数不超过 $limit$ 的方案数。

首先显然地，我们有总方案数 $C^{k-1}_{n-1}$ （使用隔板法）

然后，我们知道这其中有一些方案是不合法的，需要排除它们。

比如说假如有 $p$ 个组的元素个数超过了 $limit$ ，那我们就要把这些方案去掉。那么这些方案的个数怎么计算呢？

首先我们为这 $p$ 个组至少得分配 $limit$ 个元素，这样预处理之后，我们再对所有组进行隔板法处理分配。通过这样处理，我们就做到了至少有 $p$ 个组是超限的分配。

具体地，为这 $p$ 个组分配 $limit$ 个球，方案数为 $C^{p}_{k}$ （从 $k$ 个组中选 $p$ 个出来）

然后剩下的就是 $n - p \cdot limit$ 个元素，需要分配到所有组中，方案数就是 $C^{k-1}_{n- p \cdot limit - 1}$

然后我们发现，诶，感觉有点不对啊，我们先拿 $p = 0$ 即总方案数的情况，然后减去 $p = 1$ 的情况。

假设我们此时减去了“第一个组超限”这种情况，不难发现，这种情况中同样也包含了“第一个和第二个组都超限”的情况，此时如果我们再减去“第二个组超限”的情况，就可以发现“第一个第二个组都超限的情况被减了两次。

所以此时我们就需要把这种情况的数量加回来，也就是 $p = 2$ 时的方案数。但是此时又出现了问题：“1,2,3组同时超限”的情况在 $p = 1$ 时被减了三次（ $C^{1}_{3} = 3$ ），在 $p = 2$ 时又被加了三次（ $C^{2}_{3} = 3$ ），两相抵消，则三个组同时超限的情况消失了，所以我们又需要再减去 $p = 3$ 的情况。

如此反复，最终的方案数就是

f(n,k,limit) = \sum^{k}_{p=0} (-1)^{p} \cdot C^{p}_{k} \cdot C^{k-1}_{n - p \cdot limit - 1}

总方案：

\sum_{i,j} f(zero,i,limit) \cdot f(one,j,limit) \cdot g(i,j)

其中

g(x) = \begin{cases} 2, & i=j \\ 1, & |i-j| = 1 \\ 0, & \text{other} \end{cases}

算法实现

为了快速计算组合数，我们需要预处理出阶乘的逆元，具体如下：

$Solution$

class Solution {
private:
    const int mod=1e9+7;
    long long fact[2005],inv_fact[2005];

    long long quick_pow(long long a,long long b,long long p)    //快速幂
    {
        long long res=1%p;
        while(b)
        {
            if(b&1)
                res=(res*a)%p;
            a=(a*a)%p;
            b>>=1;
        }

        return res;
    }

    void precompute(int n)  //O(N)预处理阶乘和逆元
    {
        fact[0]=1;
        for(int i=1;i<=n;i++)
            fact[i]=(fact[i-1] * i) % mod;

        inv_fact[n]=quick_pow(fact[n], mod-2, mod);
        for(int i=n-1;i>=0;i--)
            inv_fact[i]=(inv_fact[i+1] * (i + 1))%mod;
    }

    long long ncr(int n,int r)  //计算组合数
    {
        if(r<0 || r>n)
            return 0;

        return fact[n]*inv_fact[r]%mod*inv_fact[n-r]%mod;
    }

    long long f(int n,int k,int limit)  //方案数函数
    {
        if(n < k)
            return 0;

        long long res=0;
        for(int i=0;i<=k;i++)
        {
            long long rem = n - (long long)i * limit;
            if(rem<k)
                continue;

            long long term = ncr(k,i)*ncr(rem-1,k-1)%mod;
            if(i%2==1)
                res=(res-term + mod)%mod;
            else
                res=(res+term)%mod;
        }

        return res;
    }
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        precompute(zero+one);
        long long ans=0;

        for(int i=1;i<=zero;i++)
        {
            for(int j:{i-1,i,i+1})
            {
                if(j<1 || j>one)
                    continue;

                long long way0=f(zero,i,limit);
                long long way1=f(one,j,limit);
                long long comb=way0*way1%mod;

                if(i==j)
                    ans=(ans+comb*2)%mod;
                else
                    ans=(ans+comb)%mod;
            }
        }

        return (int)ans;
    }
};

思路分析

流程概述

单色分组

算法实现

SolutionSolutionSolution

$Solution$