2026-07-15：恰好看到 K 个人的方向选择。用go语言，有 n 个人站成一排，编号依次为 0 到 n-1。每个人都必须独立地选定一个朝向：要么朝

2026-07-15：恰好看到 K 个人的方向选择。用go语言，有 n 个人站成一排，编号依次为 0 到 n-1。每个人都必须独立地选定一个朝向：要么朝左，要么朝右。如果一个人朝左，那么他只能被站在他右边的人看到；如果朝右，那么他只能被站在他左边的人看到。

现在，我们关注站在位置 pos 的那个人。对于站在他左边的每一个人（即编号小于 pos 的人），只有当那个人朝左时，他才能看到。对于站在他右边的每一个人（即编号大于 pos 的人），只有当那个人朝右时，他才能看到。

请你计算一共有多少种为所有人分配朝向的方案，能使得位于 pos 的人恰好看到 k 个人。由于答案可能很大，请将结果对 1000000007 取模后返回。

1 <= n <= 100000。

0 <= pos, k <= n – 1。

输入： n = 3, pos = 1, k = 0。

输出： 2。

解释：

下标 0 在 pos = 1 的左侧，下标 2 在 pos = 1 的右侧。

为了看到 k = 0 个人，下标 0 必须选择 ‘R’，且下标 2 必须选择 ‘L’，这样两人都不可见。

位于下标 1 的人可以选择 ‘L’ 或 ‘R’，因为这不会影响计数。因此，答案是 2。

题目来自力扣3881。

一、题意拆解 1. 人群划分

总共有n个人，下标0 ~ n-1，目标人物在pos位置，整排被分成三段独立人群：

1.左区L：编号< pos，总人数left = pos人

2.目标人P：编号pos，1个人

3.右区R：编号> pos，总人数right = n - pos - 1人

2. 可见规则（核心判定条件）

设目标人P能看到的总人数 = 左侧可见人数 + 右侧可见人数，要求总和恰好等于k：

1. 左侧任意一人（左区）：只有朝左L，P才能看见他；朝右R则看不见。

2. 右侧任意一人（右区）：只有朝右R，P才能看见他；朝左L则看不见。

3. 目标人P自己朝左/朝右完全不影响可见计数，两种朝向都合法，固定贡献乘以系数2。

3. 拆分数学方程

设：

• 从左区left人中选出x个人朝左（被P看见），剩余left - x人朝右（看不见）

• 从右区right人中选出y个人朝右（被P看见），剩余right - y人朝左（看不见）
约束条件：x + y = k，其中0 ≤ x ≤ left、0 ≤ y ≤ right。

总方案 = 所有满足x+y=k的组合方案之和 × 目标人自身2种朝向。
对一组合法x,y的局部方案计算：

1. 左区选x人可见：组合数C(left, x)；剩下人强制不可见，朝向唯一确定，无额外乘法。

2. 右区选y人可见：组合数C(right, y)；剩下人强制不可见，朝向唯一确定，无额外乘法。

3. 单组贡献：C(left, x) × C(right, y)

4. 全部合法x累加总和：sum_{x} C(left, x) × C(right, k-x)（x范围保证y合法）

5. 最终答案 = 累加总和 × 2 再对 1e9+7 取模。

样例验证（n=3, pos=1, k=0）

• left = pos = 1（下标0），right = 3-1-1 = 1（下标2）

• k=0，要求x+y=0，只能 x=0,y=0

• C(1,0)=1：左边1个人全部不可见，必须朝右，仅1种方案

• C(1,0)=1：右边1个人全部不可见，必须朝左，仅1种方案

• 累加和 = 1×1 = 1

• 目标人两种朝向：1 × 2 = 2，和样例输出一致。

二、预处理阶乘与逆元组合数完整流程（分步详解）

题目n上限1e5，多次查询组合数，采用阶乘+阶乘逆元O(n)预处理，O(1)单次求组合数，分两大阶段：预处理阶段 + 计算答案阶段。

阶段1：全局预处理（init函数执行，程序启动只跑一次）

模数mod = 1e9+7，最大预处理长度mx = 100001覆盖n上限1e5。

步骤1：预处理阶乘数组 fac[]

fac[i]存储i! mod mod

1. 初始化边界：0的阶乘fac[0] = 1

2. 循环i从1到mx-1：
fac[i] = fac[i-1] × i % mod
递推算出 1!,2!,3!…100000!，全部取模防止溢出。

步骤2：预处理阶乘逆元数组 invF[]

模意义下，阶乘逆元满足invF[i] = (i!)^{-1} mod mod，使用费马小定理：质数mod下a^{-1}=a^{mod-2} mod mod。

1. 先求最大阶乘的逆元：invF[mx-1] = pow(fac[mx-1], mod-2)
pow函数是快速幂，二分幂次快速计算高次取模。

2. 逆推递推所有逆元：i从mx-1倒推到1
公式推导：
(i-1)!^{-1} = i × (i!)^{-1} mod mod
即invF[i-1] = invF[i] × i % mod
从最大数往回算，不用重复快速幂，线性时间完成全部逆元。

步骤3：快速幂pow函数原理（预处理依赖）

输入底数x、指数n，返回x^n mod mod：

1. 结果res初始为1

2. 循环分解指数n二进制：每次n整除2

• 当前二进制最低位为1：res = res × x % mod，累积当前底数

• 底数平方取模：x = x × x % mod

3. 循环结束返回res，时间O(logn)。

阶段2：组合数查询函数 comb(n,m) O(1) 单次调用

输入总人数n、选取m人，返回*****) mod mod：

1. 边界判断：m<0 或 m>n，不存在合法组合，直接返回0

2. 合法情况公式：

模除法转乘法逆元：
comb = fac[n] × invF[m] % mod × invF[n-m] % mod

阶段3：主逻辑 countVisiblePeople 计算答案（原题核心逻辑）

入参n,pos,k：

1. 计算左区人数 left = pos；右区人数 right = n-pos-1

2. 枚举所有合法x（左侧可见人数）：
x的合法区间：x ≥ 0，y=k-x ≥ 0，x ≤ left，y ≤ right
即max(0, k-right) ≤ x ≤ min(left, k)
对每个x，y=k-x，累加comb(left, x) * comb(right, y) mod mod，得到总基础方案和sum

3. 目标人pos有朝左、朝右2种朝向，答案 = sum × 2 % mod

阶段4：main函数流程

1. 给定输入n,pos,k

2. 调用countVisiblePeople计算总方案数

3. 打印输出结果

三、时间复杂度完整分布 1. 预处理 init 总时间 O(mx) = O(1e5)

1. 阶乘数组循环：O(mx)，mx=1e5+1

2. 快速幂计算最大逆元：O(log mod) ≈ O(30)，常数可忽略

3. 逆元倒推循环：O(mx)
预处理整体线性O(1e5)，程序启动仅执行1次。

2. 单次查询计算 countVisiblePeople 时间

1. 枚举合法x求和：枚举次数最多不超过 min(left, k)+1，最坏极端情况O(n)；
但n上限1e5，单次查询最多1e5次循环，每次循环两次O(1) comb调用。

2. comb函数单次O(1)，仅三次乘法取模。

3. 快速幂仅预处理阶段使用，查询阶段无log开销。

3. 全局总时间复杂度总结

• 预处理：O(1e5)

• 单次询问：最坏 O(n)
若只运行一组输入（main单组测试），整体时间复杂度：O(1e5 + n)，n≤1e5，等价O(1e5)。

四、额外空间复杂度分布

全局开辟两个定长数组，无动态内存：

1. fac数组：长度 mx=100001，存储int，空间 O(mx)

2. invF数组：长度 mx=100001，存储int，空间 O(mx)
其余变量（循环i、临时乘积、n/pos/k/left/right/sum等）均为单个int常数空间 O(1)。

总额外空间复杂度：O(mx) = O(1e5)。

Go完整代码如下：

package main

 import (
    "fmt"
)

 const mod = 1_000_000_007
const mx = 100_001

 var fac [mx]int// fac[i] = i!
var invF [mx]int// invF[i] = i!^-1 = pow(i!, mod-2)

 func init() {
    fac[0] = 1
    for i := 1; i < mx; i++ {
        fac[i] = fac[i-1] * i % mod
    }

     invF[mx-1] = pow(fac[mx-1], mod-2)
    for i := mx - 1; i > 0; i-- {
        invF[i-1] = invF[i] * i % mod
    }
}

 func pow(x, n int)int {
    res := 1
    for ; n > 0; n /= 2 {
        if n%2 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

 // 从 n 个数中选 m 个数的方案数
func comb(n, m int)int {
    if m < 0 || m > n {
        return0
    }
    return fac[n] * invF[m] % mod * invF[n-m] % mod
}

 func countVisiblePeople(n, _, k int)int {
    return comb(n-1, k) * 2 % mod
}

 func main() {
    n := 3
    pos := 1
    k := 0
    result := countVisiblePeople(n, pos, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 MOD = 1_000_000_007
MX = 100_001

 # 预计算阶乘和逆阶乘
fac = [1] * MX
invF = [1] * MX

 fac[0] = 1
for i in range(1, MX):
    fac[i] = fac[i-1] * i % MOD

 invF[MX-1] = pow(fac[MX-1], MOD-2, MOD)  # 内置快速幂支持取模
for i in range(MX-1, 0, -1):
    invF[i-1] = invF[i] * i % MOD

 def comb(n: int, m: int) -> int:
    """从 n 个数中选 m 个数的方案数（模 MOD）"""
    if m < 0 or m > n:
        return0
    return fac[n] * invF[m] % MOD * invF[n-m] % MOD

 def countVisiblePeople(n: int, pos: int, k: int) -> int:
    return comb(n-1, k) * 2 % MOD

 def main():
    n = 3
    pos = 1
    k = 0
    result = countVisiblePeople(n, pos, k)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

using namespace std;

 const long long MOD = 1'000'000'007LL;
const int MX = 100'001;

 long long fac[MX];   // fac[i] = i!
long long invF[MX];  // invF[i] = (i!)^(-1) mod MOD

 // 快速幂取模
long long modpow(long long a, long long e) {
    long long res = 1;
    while (e > 0) {
        if (e & 1) res = res * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return res;
}

 // 初始化阶乘和逆阶乘（对应 Go 的 init 函数）
void init() {
    fac[0] = 1;
    for (int i = 1; i < MX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }

     invF[MX - 1] = modpow(fac[MX - 1], MOD - 2);
    for (int i = MX - 1; i > 0; i--) {
        invF[i - 1] = invF[i] * i % MOD;
    }
}

 // 组合数 C(n, m) 模 MOD
long long comb(int n, int m) {
    if (m < 0 || m > n) return0;
    return fac[n] * invF[m] % MOD * invF[n - m] % MOD;
}

 // 原 countVisiblePeople，pos 参数未使用（用注释忽略）
long long countVisiblePeople(int n, int/*pos*/, int k) {
    return comb(n - 1, k) * 2 % MOD;
}

 int main() {
    init();  // 必须显式调用初始化

     int n = 3;
    int pos = 1;
    int k = 0;
    long long result = countVisiblePeople(n, pos, k);
    cout << result << '\n';

     return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。