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

福大大架构师每日一题

发布于 2026-07-15 15:07:20

430

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++完整代码如下：

#include <bits/stdc++.h>
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;
}