关注【索引目录】服务号，更多精彩内容等你来探索！
LeetCode 3405 |困难|组合数学
问题摘要
给出三个整数：
n：数组的长度 m：值的范围 [1, m]k：相邻相等对的数量
您必须找到“好数组”的总数，其中：
-
每个元素都位于范围内 [1, m] -
恰好 k指标i（其中1 ≤ i < n）满足arr[i - 1] == arr[i]
由于结果可能很大，因此返回计数模数10⁹ + 7。
直觉
构造一个有效的数组：
-
选择相等的 k位置（从可能的相邻对中）。n - 1 -
第一个元素可以是从 1到的任意值m。 -
对于剩余的每个 n - 1 - k位置（必须与前一个元素不同），都有m - 1选项。
因此，此类数组的总数为：
C(n - 1, k) × m × (m - 1)^(n - 1 - k)在哪里：
C(n - 1, k)k是选择相邻位置相等的方式的数量。 -
其余位置必须不同，因此 m - 1每个元素的选择必须不同。 -
对于较大的约束，需要模逆和指数运算。
C++ 代码（含解释）
const int MOD = 1e9 + 7;
const int MX = 1e5 + 1;
long long fact[MX], inv_fact[MX];
class Solution {
long long qpow(long long x, int n) {
long long res = 1;
while (n) {
if (n & 1) res = res * x % MOD;
x = x * x % MOD;
n >>= 1;
}
return res;
}
long long comb(int n, int r) {
return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
}
void init() {
if (fact[0]) return; // Already initialized
fact[0] = 1;
for (int i = 1; i < MX; ++i)
fact[i] = fact[i - 1] * i % MOD;
inv_fact[MX - 1] = qpow(fact[MX - 1], MOD - 2);
for (int i = MX - 1; i > 0; --i)
inv_fact[i - 1] = inv_fact[i] * i % MOD;
}
public:
int countGoodArrays(int n, int m, int k) {
init();
return comb(n - 1, k) * m % MOD * qpow(m - 1, n - 1 - k) % MOD;
}
};重点说明：
init()预先计算阶乘和逆阶乘。 qpow()处理模下的快速指数运算。 -
时间复杂度： O(n)针对预计算，O(1)每个查询。
JavaScript 代码
const MOD = 1e9 + 7;
const MAX = 1e5 + 1;
const fact = new Array(MAX).fill(1);
const invFact = new Array(MAX).fill(1);
function modPow(x, n) {
let res = 1;
while (n) {
if (n & 1) res = res * x % MOD;
x = x * x % MOD;
n >>= 1;
}
return res;
}
function init() {
for (let i = 1; i < MAX; ++i)
fact[i] = fact[i - 1] * i % MOD;
invFact[MAX - 1] = modPow(fact[MAX - 1], MOD - 2);
for (let i = MAX - 2; i >= 0; --i)
invFact[i] = invFact[i + 1] * (i + 1) % MOD;
}
function comb(n, k) {
return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}
var countGoodArrays = function(n, m, k) {
init();
return comb(n - 1, k) * m % MOD * modPow(m - 1, n - 1 - k) % MOD;
};Python代码
MOD = 10**9 + 7
MAX = 10**5 + 1
fact = [1] * MAX
inv_fact = [1] * MAX
def modinv(x):
return pow(x, MOD - 2, MOD)
def init():
for i in range(1, MAX):
fact[i] = fact[i - 1] * i % MOD
inv_fact[MAX - 1] = modinv(fact[MAX - 1])
for i in range(MAX - 2, -1, -1):
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
def comb(n, k):
if k < 0 or k > n:
return 0
return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD
class Solution:
def countGoodArrays(self, n: int, m: int, k: int) -> int:
init()
return comb(n - 1, k) * m % MOD * pow(m - 1, n - 1 - k, MOD) % MOD最后的想法
这个问题是应用的一个清晰的例子：
-
模块化组合 -
快速指数运算 -
带逆模的阶乘预计算
一旦正确分解，问题就不再仅仅关乎纯粹的实现，而是关乎数学洞察力。对于任何基于组合数学且约束条件不超过 的问题，这都是一个绝佳的模板10⁵。