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位置整排被分成三段独立人群左区L编号 pos总人数left pos人目标人P编号pos1个人右区R编号 pos总人数right n - pos - 1人2. 可见规则核心判定条件设目标人P能看到的总人数 左侧可见人数 右侧可见人数要求总和恰好等于k左侧任意一人左区只有朝左LP才能看见他朝右R则看不见。右侧任意一人右区只有朝右RP才能看见他朝左L则看不见。目标人P自己朝左/朝右完全不影响可见计数两种朝向都合法固定贡献乘以系数2。3. 拆分数学方程设从左区left人中选出x个人朝左被P看见剩余left - x人朝右看不见从右区right人中选出y个人朝右被P看见剩余right - y人朝左看不见约束条件x y k其中0 ≤ x ≤ left、0 ≤ y ≤ right。总方案 所有满足xyk的组合方案之和 × 目标人自身2种朝向。对一组合法x,y的局部方案计算左区选x人可见组合数C(left, x)剩下人强制不可见朝向唯一确定无额外乘法。右区选y人可见组合数C(right, y)剩下人强制不可见朝向唯一确定无额外乘法。单组贡献C(left, x) × C(right, y)全部合法x累加总和sum_{x} C(left, x) × C(right, k-x)x范围保证y合法最终答案 累加总和 × 2 再对 1e97 取模。样例验证n3, pos1, k0left pos 1下标0right 3-1-1 1下标2k0要求xy0只能 x0,y0C(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 1e97最大预处理长度mx 100001覆盖n上限1e5。步骤1预处理阶乘数组 fac[]fac[i]存储i! mod mod初始化边界0的阶乘fac[0] 1循环i从1到mx-1fac[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。先求最大阶乘的逆元invF[mx-1] pow(fac[mx-1], mod-2)pow函数是快速幂二分幂次快速计算高次取模。逆推递推所有逆元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结果res初始为1循环分解指数n二进制每次n整除2当前二进制最低位为1res res × x % mod累积当前底数底数平方取模x x × x % mod循环结束返回res时间O(logn)。阶段2组合数查询函数 comb(n,m) O(1) 单次调用输入总人数n、选取m人返回*****) mod mod边界判断m0 或 mn不存在合法组合直接返回0合法情况公式∗∗∗∗∗)n!m!⋅(n−m)!mod mod*****) \frac{n!}{m!·(n-m)!} \mod mod∗∗∗∗∗)m!⋅(n−m)!n!​modmod模除法转乘法逆元comb fac[n] × invF[m] % mod × invF[n-m] % mod阶段3主逻辑 countVisiblePeople 计算答案原题核心逻辑入参n,pos,k计算左区人数 left pos右区人数 right n-pos-1枚举所有合法x左侧可见人数x的合法区间x ≥ 0yk-x ≥ 0x ≤ lefty ≤ right即max(0, k-right) ≤ x ≤ min(left, k)对每个xyk-x累加comb(left, x) * comb(right, y) mod mod得到总基础方案和sum目标人pos有朝左、朝右2种朝向答案 sum × 2 % mod阶段4main函数流程给定输入n,pos,k调用countVisiblePeople计算总方案数打印输出结果三、时间复杂度完整分布1. 预处理 init 总时间 O(mx) O(1e5)阶乘数组循环O(mx)mx1e51快速幂计算最大逆元O(log mod) ≈ O(30)常数可忽略逆元倒推循环O(mx)预处理整体线性O(1e5)程序启动仅执行1次。2. 单次查询计算 countVisiblePeople 时间枚举合法x求和枚举次数最多不超过 min(left, k)1最坏极端情况O(n)但n上限1e5单次查询最多1e5次循环每次循环两次O(1) comb调用。comb函数单次O(1)仅三次乘法取模。快速幂仅预处理阶段使用查询阶段无log开销。3. 全局总时间复杂度总结预处理O(1e5)单次询问最坏 O(n)若只运行一组输入main单组测试整体时间复杂度O(1e5 n)n≤1e5等价O(1e5)。四、额外空间复杂度分布全局开辟两个定长数组无动态内存fac数组长度 mx100001存储int空间 O(mx)invF数组长度 mx100001存储int空间 O(mx)其余变量循环i、临时乘积、n/pos/k/left/right/sum等均为单个int常数空间 O(1)。总额外空间复杂度O(mx) O(1e5)。Go完整代码如下packagemainimport(fmt)constmod1_000_000_007constmx100_001varfac[mx]int// fac[i] i!varinvF[mx]int// invF[i] i!^-1 pow(i!, mod-2)funcinit(){fac[0]1fori:1;imx;i{fac[i]fac[i-1]*i%mod}invF[mx-1]pow(fac[mx-1],mod-2)fori:mx-1;i0;i--{invF[i-1]invF[i]*i%mod}}funcpow(x,nint)int{res:1for;n0;n/2{ifn%20{resres*x%mod}xx*x%mod}returnres}// 从 n 个数中选 m 个数的方案数funccomb(n,mint)int{ifm0||mn{return0}returnfac[n]*invF[m]%mod*invF[n-m]%mod}funccountVisiblePeople(n,_,kint)int{returncomb(n-1,k)*2%mod}funcmain(){n:3pos:1k:0result:countVisiblePeople(n,pos,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-MOD1_000_000_007MX100_001# 预计算阶乘和逆阶乘fac[1]*MX invF[1]*MX fac[0]1foriinrange(1,MX):fac[i]fac[i-1]*i%MOD invF[MX-1]pow(fac[MX-1],MOD-2,MOD)# 内置快速幂支持取模foriinrange(MX-1,0,-1):invF[i-1]invF[i]*i%MODdefcomb(n:int,m:int)-int:从 n 个数中选 m 个数的方案数模 MODifm0ormn:return0returnfac[n]*invF[m]%MOD*invF[n-m]%MODdefcountVisiblePeople(n:int,pos:int,k:int)-int:returncomb(n-1,k)*2%MODdefmain():n3pos1k0resultcountVisiblePeople(n,pos,k)print(result)if__name____main__:main()C完整代码如下#includebits/stdc.husingnamespacestd;constlonglongMOD1000000007LL;constintMX100001;longlongfac[MX];// fac[i] i!longlonginvF[MX];// invF[i] (i!)^(-1) mod MOD// 快速幂取模longlongmodpow(longlonga,longlonge){longlongres1;while(e0){if(e1)resres*a%MOD;aa*a%MOD;e1;}returnres;}// 初始化阶乘和逆阶乘对应 Go 的 init 函数voidinit(){fac[0]1;for(inti1;iMX;i){fac[i]fac[i-1]*i%MOD;}invF[MX-1]modpow(fac[MX-1],MOD-2);for(intiMX-1;i0;i--){invF[i-1]invF[i]*i%MOD;}}// 组合数 C(n, m) 模 MODlonglongcomb(intn,intm){if(m0||mn)return0;returnfac[n]*invF[m]%MOD*invF[n-m]%MOD;}// 原 countVisiblePeoplepos 参数未使用用注释忽略longlongcountVisiblePeople(intn,int/*pos*/,intk){returncomb(n-1,k)*2%MOD;}intmain(){init();// 必须显式调用初始化intn3;intpos1;intk0;longlongresultcountVisiblePeople(n,pos,k);coutresult\n;return0;}