北京海淀区信息学竞赛 · 2024 北京市海淀区信息学竞赛（初赛）试题 第 21 题

对于下面的程序段，如果输入 $2$ 则输出的是（ ）。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll f(int n, int k) {
    ll res = 1;
    for (int i = 1; i <= k; i++) res = res * (n + 1 - i) / i;
    return res;
}

int main() {
    int m;
    ll c1, c2;
    scanf("%d", &m);
    c1 = f(m + 2, 3);
    c2 = f(m + 4, 5);
    printf("%lld", c1 * c2);
    return 0;
}

这题就是考你手算组合数的能力，别被代码吓住。输入 m=2 时，c1 其实是 C(4,3)，c2 是 C(6,5)，算出这两个数相乘就是答案。

最容易栽跟头的地方是把循环里的除法当成浮点除法，或者没注意到整数除法的截断特性，导致中间结果算错。还有很多人会搞混 n 和 k 的顺序，把 C(4,3) 算成 C(3,4)，最后乘起来肯定不对。另外，很多人会忽略变量初始化，以为 res 是 0 开始算的，其实 res 初始是 1，这是组合数公式的标准起手式。

这道题考查的是程序阅读与模拟执行的能力，核心知识点是组合数的计算过程以及 C++ 中整数除法的特性。命题人很喜欢把简单的数学公式包装成循环代码，让你去跟踪变量的变化，这既考语法也考数学直觉。拿到题先想什么？别急着敲键盘，先在脑子里把 f 函数翻译成数学语言。函数 f(n, k) 的循环里，res 初始为 1，每次迭代 res = res * (n + 1 - i) / i。这其实就是 C(n+1, k) 的递推式，也就是组合数 C(n+1, k) = C(n, k-1) * (n+1) / k。所以 f(m+2, 3) 算的就是 C(m+2+1, 3) = C(m+3, 3)，f(m+4, 5) 算的就是 C(m+4+1, 5) = C(m+5, 5)。题目输入 m=2，那 c1 = C(5, 3)，c2 = C(7, 5)。C(5, 3) = 10，C(7, 5) = 21，10 * 21 = 210？不对，等等，我刚才公式推导好像有点绕。直接模拟更稳妥：f(4, 3) 时，i=1，res=1*(4+1-1)/1=4；i=2，res=4*(4+1-2)/2=4*3/2=6；i=3，res=6*(4+1-3)/3=6*2/3=4。所以 c1=4。f(6, 5) 时，i=1，res=1*(6+1-1)/1=6；i=2，res=6*(6+1-2)/2=6*5/2=15；i=3，res=15*(6+1-3)/3=15*4/3=20；i=4，res=20*(6+1-4)/4=20*3/4=15；i=5，res=15*(6+1-5)/5=15*2/5=6。所以 c2=6。c1*c2=4*6=24。这个结果对应选项 D。命题人挖坑的地方在于，很多人会误以为 res 在每次乘法后都是整数，其实整数除法会截断小数部分，比如 6*3/2=9，但代码里是 6*5/2=15，没问题，因为分子分母刚好整除。但如果是 f(5, 4)，i=3 时 res=10*2/3=6，这里 10*2=20，20/3=6 余 2，截断后是 6，这跟数学上的 C(6,4)=15 不一样，说明代码算的是 C(n+1, k) 的中间过程，最后一步才是完整的组合数。所以一定要按代码顺序一步步算，不能跳步。考频方面，组合数相关题目在 CSP-J/S 中属于高频考点，近五年平均每年出现 2-3 次，常以程序模拟或数学推理形式出现，2024 年海淀区赛再次考查，说明命题人认为这是基础中的基础，必须扎实掌握。预测的话，未来这类题可能会更隐蔽，比如把组合数嵌套在递归里，或者用位运算模拟乘法除法，但核心还是考你对组合数公式的理解和模拟执行的能力。总之，这题答案就是 D，24。