Medium
题目描述
给定三个整数 n、pos 和 k。
有 n 个人站成一排，索引从 0 到 n - 1。每个人独立选择一个方向：
- ‘L’：只对右侧的人可见
- ‘R’：只对左侧的人可见
索引为 pos 的人看到其他人的规则如下：
- 对于索引
i < pos的人，当且仅当他们选择 ‘L’ 时才可见 - 对于索引
i > pos的人，当且仅当他们选择 ‘R’ 时才可见
返回使得索引为 pos 的人恰好能看到 k 个人的可能方向分配数量。
由于答案可能很大，返回结果对 10^9 + 7 取模。
示例 1：
输入：n = 3, pos = 1, k = 0
输出：2
解释：
索引 0 在 pos = 1 的左侧，索引 2 在 pos = 1 的右侧。
要看到 k = 0 个人，索引 0 必须选择 'R'，索引 2 必须选择 'L'，保持都不可见。
索引 1 的人可以选择 'L' 或 'R'，因为这不影响计数。因此答案是 2。
示例 2：
输入：n = 3, pos = 2, k = 1
输出：4
解释：
索引 0 和索引 1 在 pos = 2 的左侧，右侧没有索引。
要看到 k = 1 个人，索引 0 或索引 1 中恰好有一个必须选择 'L'，另一个必须选择 'R'。
有 2 种方法选择左侧哪个索引可见。
索引 2 的人可以选择 'L' 或 'R'，因为这不影响计数。因此答案是 2 + 2 = 4。
示例 3：
输入：n = 1, pos = 0, k = 0
输出：2
解释：
pos = 0 的左侧或右侧都没有索引。
要看到 k = 0 个人，不需要额外条件。
索引 0 的人可以选择 'L' 或 'R'。因此答案是 2。
约束条件：
- 1 <= n <= 10^5
- 0 <= pos, k <= n - 1
解题思路
这是一道组合数学问题。我们需要分析在位置 pos 的人能看到恰好 k 个人的所有可能方案数。
核心思路：
分析可见性规则：
- 左侧（索引 < pos）的人选择 ‘L’ 才对 pos 可见
- 右侧（索引 > pos）的人选择 ‘R’ 才对 pos 可见
分割问题：
- 设左侧有
left = pos个人，右侧有right = n - pos - 1个人 - 要看到恰好
k个人，可以从左侧选择i个可见，从右侧选择k-i个可见（0 ≤ i ≤ k）
- 设左侧有
计算每种分配方案：
- 从左侧
left个人中选择i个可见：C(left, i) - 从右侧
right个人中选择k-i个可见：C(right, k-i) - 左侧选中的
i个人必须选 ‘L’（1种选择） - 左侧未选中的
left-i个人可以选 ‘L’ 或 ‘R’（2^(left-i) 种选择） - 右侧选中的
k-i个人必须选 ‘R’（1种选择） - 右侧未选中的
right-(k-i)个人可以选 ‘L’ 或 ‘R’（2^(right-k+i) 种选择） - pos 位置的人可以选 ‘L’ 或 ‘R’（2种选择）
- 从左侧
最终公式： 对所有有效的 i 求和：∑ C(left,i) × C(right,k-i) × 2^(left-i) × 2^(right-k+i) × 2
推荐解法：使用预计算组合数和快速幂的方法，时间复杂度 O(k)。
代码实现
class Solution {
public:
int countVisiblePeople(int n, int pos, int k) {
const int MOD = 1e9 + 7;
int left = pos;
int right = n - pos - 1;
if (k > left + right) return 0;
// 预计算阶乘和逆元
vector<long long> fact(n + 1), inv_fact(n + 1);
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] = power(fact[n], MOD - 2);
for (int i = n - 1; i >= 0; i--) {
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}
auto C = [&](int n, int k) -> long long {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
};
long long result = 0;
for (int i = 0; i <= k; i++) {
if (i > left || k - i > right) continue;
long long ways = C(left, i) * C(right, k - i) % MOD;
ways = ways * power(2, left - i + right - k + i + 1) % MOD;
result = (result + ways) % MOD;
}
return result;
}
};
class Solution:
def countVisiblePeople(self, n: int, pos: int, k: int) -> int:
MOD = 10**9 + 7
left = pos
right = n - pos - 1
if k > left + right:
return 0
# 预计算阶乘和逆元
fact = [1] * (n + 1)
for i in range(1, n + 1):
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 + 1)
inv_fact[n] = power(fact[n], MOD - 2)
for i in range(n - 1, -1, -1):
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
def C(n, k):
if k < 0 or k > n:
return 0
return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD
result = 0
for i in range(k + 1):
if i > left or k - i > right:
continue
ways = C(left, i) * C(right, k - i) % MOD
ways = ways * power(2, left - i + right - k + i + 1) % MOD
result = (result + ways) % MOD
return result
public class Solution {
public int CountVisiblePeople(int n, int pos, int k) {
const int MOD = 1000000007;
int left = pos;
int right = n - pos - 1;
if (k > left + right) return 0;
// 预计算阶乘和逆元
long[] fact = new long[n + 1];
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 + 1];
invFact[n] = Power(fact[n], MOD - 2);
for (int i = n - 1; i >= 0; i--) {
invFact[i] = invFact[i + 1] * (i + 1) % MOD;
}
long C(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}
long result = 0;
for (int i = 0; i <= k; i++) {
if (i > left || k - i > right) continue;
long ways = C(left, i) * C(right, k - i) % MOD;
ways = ways * Power(2, left - i + right - k + i + 1) % MOD;
result = (result + ways) % MOD;
}
return (int)result;
}
}
var countVisiblePeople = function(n, pos, k) {
const MOD = 1e9 + 7;
const left = pos;
const right = n - pos - 1;
if (k > left + right) return 0;
// 预计算阶乘和逆元
const fact = new Array(n + 1);
fact[0] = 1;
for (let i = 1; i <= n; i++) {
fact[i] = (fact[i-1] * i) % MOD;
}
const power = (base, exp) => {
let result = 1;
while (exp > 0) {
if (exp & 1) result = (result * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return result;
};
const invFact = new Array(n + 1);
invFact[n] = power(fact[n], MOD - 2);
for (let i = n - 1; i >= 0; i--) {
invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
}
const C = (n, k) => {
if (k < 0 || k > n) return 0;
return (fact[n] * invFact[k] % MOD * invFact[n - k]) % MOD;
};
let result = 0;
for (let i = 0; i <= k; i++) {
if (i > left || k - i > right) continue;
let ways = (C(left, i) * C(right, k - i)) % MOD;
ways = (ways * power(2, left - i + right - k + i + 1)) % MOD;
result = (result + ways) % MOD;
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n + k) | 预计算阶乘需要O(n)，主循环需要O(k)，组合数计算和快速幂都是O(1) |
| 空间复杂度 | O(n) | 存储阶乘和逆元数组需要O(n)空间 |