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人
设目标人P能看到的总人数 = 左侧可见人数 + 右侧可见人数，要求总和恰好等于k：
1. 左侧任意一人（左区）：只有朝左L，P才能看见他；朝右R则看不见。
2. 右侧任意一人（右区）：只有朝右R，P才能看见他；朝左L则看不见。
3. 目标人P自己朝左/朝右完全不影响可见计数，两种朝向都合法，固定贡献乘以系数2。
设：
• 从左区
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 取模。
• 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] = 12. 循环i从1到mx-1：
fac[i] = fac[i-1] × i % mod
递推算出 1!,2!,3!...100000!，全部取模防止溢出。
模意义下，阶乘逆元满足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
从最大数往回算，不用重复快速幂，线性时间完成全部逆元。
输入底数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
入参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，得到总基础方案和sum3. 目标人pos有朝左、朝右2种朝向，答案 = sum × 2 % mod
1. 给定输入n,pos,k
2. 调用countVisiblePeople计算总方案数
3. 打印输出结果
1. 阶乘数组循环：O(mx)，mx=1e5+1
2. 快速幂计算最大逆元：O(log mod) ≈ O(30)，常数可忽略
3. 逆元倒推循环：O(mx)
预处理整体线性O(1e5)，程序启动仅执行1次。
1. 枚举合法x求和：枚举次数最多不超过 min(left, k)+1，最坏极端情况O(n)；
但n上限1e5，单次查询最多1e5次循环，每次循环两次O(1) comb调用。2. comb函数单次O(1)，仅三次乘法取模。
3. 快速幂仅预处理阶段使用，查询阶段无log开销。
• 预处理：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助力您的未来发展。
热门跟贴