Hard

题目描述

给你三个整数 n、m、k。大小为 n 的好数组 arr 定义如下：

  • arr 中的每个元素都在闭区间 [1, m] 内。
  • 恰好有 k 个下标 i（其中 1 <= i < n）满足条件 arr[i - 1] == arr[i]。

返回可以形成的好数组的数目。

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

示例 1：

输入：n = 3, m = 2, k = 1
输出：4
解释：有 4 个好数组。它们是 [1, 1, 2]、[1, 2, 2]、[2, 1, 1] 和 [2, 2, 1]。
因此，答案是 4。

示例 2：

输入：n = 4, m = 2, k = 2
输出：6
解释：好数组有 [1, 1, 1, 2]、[1, 1, 2, 2]、[1, 2, 2, 2]、[2, 1, 1, 1]、[2, 2, 1, 1] 和 [2, 2, 2, 1]。
因此，答案是 6。

示例 3：

输入：n = 5, m = 2, k = 0
输出：2
解释：好数组是 [1, 2, 1, 2, 1] 和 [2, 1, 2, 1, 2]。因此，答案是 2。

约束条件：

  • 1 <= n <= 10^5
  • 1 <= m <= 10^5
  • 0 <= k <= n - 1

解题思路

解题思路

这是一道典型的组合数学问题。我们需要构造一个长度为 n 的数组，其中恰好有 k 个位置满足相邻元素相等。

核心思路：

  1. 选择匹配位置：在 n-1 个相邻位置对中选择 k 个位置使得相邻元素相等，方案数为 C(n-1, k)

  2. 分配数值：

    • 第一个位置可以选择 m 种值
    • 选中的 k 个匹配位置，后一个元素必须等于前一个元素（0 种新选择）
    • 剩余的 n-1-k 个位置，后一个元素必须不等于前一个元素，每个位置有 m-1 种选择

因此，总方案数为：C(n-1, k) × m × (m-1)^(n-1-k)

实现细节：

  • 需要预计算阶乘和逆元来高效计算组合数
  • 使用快速幂计算 (m-1)^(n-1-k)
  • 所有运算都要对 10^9+7 取模

这个解法的时间复杂度主要取决于预计算阶乘，为 O(n)，空间复杂度也是 O(n)。

代码实现

class Solution {
public:
    int countGoodArrays(int n, int m, int k) {
        const int MOD = 1000000007;
        
        // 预计算阶乘和逆元
        vector<long long> fact(n), inv_fact(n);
        fact[0] = 1;
        for (int i = 1; i < n; i++) {
            fact[i] = fact[i-1] * i % MOD;
        }
        
        auto power = [&](long long base, long long exp) -> long long {
            long long result = 1;
            while (exp > 0) {
                if (exp & 1) result = result * base % MOD;
                base = base * base % MOD;
                exp >>= 1;
            }
            return result;
        };
        
        inv_fact[n-1] = power(fact[n-1], MOD - 2);
        for (int i = n - 2; i >= 0; i--) {
            inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
        }
        
        auto C = [&](int n, int k) -> long long {
            if (k > n || k < 0) return 0;
            return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
        };
        
        long long ways = C(n-1, k);
        ways = ways * m % MOD;
        ways = ways * power(m-1, n-1-k) % MOD;
        
        return ways;
    }
};

class Solution:
    def countGoodArrays(self, n: int, m: int, k: int) -> int:
        MOD = 10**9 + 7
        
        # 预计算阶乘
        fact = [1] * n
        for i in range(1, n):
            fact[i] = fact[i-1] * i % MOD
        
        def power(base, exp):
            result = 1
            while exp > 0:
                if exp & 1:
                    result = result * base % MOD
                base = base * base % MOD
                exp >>= 1
            return result
        
        # 计算逆元
        inv_fact = [1] * n
        inv_fact[n-1] = power(fact[n-1], MOD - 2)
        for i in range(n-2, -1, -1):
            inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
        
        def C(n, k):
            if k > n or k < 0:
                return 0
            return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD
        
        ways = C(n-1, k)
        ways = ways * m % MOD
        ways = ways * power(m-1, n-1-k) % MOD
        
        return ways

public class Solution {
    public int CountGoodArrays(int n, int m, int k) {
        const int MOD = 1000000007;
        
        // 预计算阶乘
        long[] fact = new long[n];
        fact[0] = 1;
        for (int i = 1; i < n; i++) {
            fact[i] = fact[i-1] * i % MOD;
        }
        
        long Power(long baseNum, long exp) {
            long result = 1;
            while (exp > 0) {
                if ((exp & 1) == 1) result = result * baseNum % MOD;
                baseNum = baseNum * baseNum % MOD;
                exp >>= 1;
            }
            return result;
        }
        
        // 计算逆元
        long[] invFact = new long[n];
        invFact[n-1] = Power(fact[n-1], MOD - 2);
        for (int i = n - 2; i >= 0; i--) {
            invFact[i] = invFact[i+1] * (i+1) % MOD;
        }
        
        long C(int n, int k) {
            if (k > n || k < 0) return 0;
            return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
        }
        
        long ways = C(n-1, k);
        ways = ways * m % MOD;
        ways = ways * Power(m-1, n-1-k) % MOD;
        
        return (int)ways;
    }
}

var countGoodArrays = function(n, m, k) {
    const MOD = 1000000007;
    
    // 预计算阶乘
    const fact = new Array(n);
    fact[0] = 1;
    for (let i = 1; i < n; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    
    function power(base, exp) {
        let result = 1;
        while (exp > 0) {
            if (exp & 1) result = result * base % MOD;
            base = base * base % MOD;
            exp = Math.floor(exp / 2);
        }
        return result;
    }
    
    // 计算逆元
    const invFact = new Array(n);
    invFact[n-1] = power(fact[n-1], MOD - 2);
    for (let i = n - 2; i >= 0; i--) {
        invFact[i] = invFact[i+1] * (i+1) % MOD;
    }
    
    function C(n, k) {
        if (k > n || k < 0) return 0;
        return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
    }
    
    let ways = C(n-1, k);
    ways = ways * m % MOD;
    ways = ways * power(m-1, n-1-k) % MOD;
    
    return ways;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n + log(n-1-k))
空间复杂度O(n)

说明：

  • 时间复杂度：预计算阶乘需要 O(n)，计算快速幂需要 O(log(n-1-k))
  • 空间复杂度：需要存储阶乘和逆元数组，总共 O(n) 空间

相关题目