贝壳找房 · 组合数学 · 算法编程题
贝壳找房 组合数学 t ≤ 1e5 时限 2 秒 / 256 MB

题目描述

牛牛进入了方格世界，方格世界由 n× m 个方格构成的高为 n 宽为 m 的矩形，牛牛所在的方格为 ( 1,1 ) ，而方格世界的出口在 ( n,m ) 。在方格世界中，牛牛只能向上走或者向左或向右走，而且牛牛走过的方格不能再次进入。牛牛想知道他有多少种走出方格世界的路径，答案可能很大请对 10^9+7 取模。

输入输出

输入描述
第一行为一个 t ，表示有 t 组数据。
接下来有 t 行，每行有两个数字 n 和 m 。
1≤ t ≤ 10^5,2≤ n,m≤ 10^9
输出描述
输出为 t 行，每行一个数字表示答案。

样例共 1 组

样例 1
输入
2
2 2
3 3
输出
2
9

算法解析依据一般

考点：组合数学

数据规模 t ≤ 1e5 ｜ 限制 2 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：t ≤ 1e5
  • 元素值域：n ≤ 1e9，m ≤ 1e9（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：2 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：组合数学

用计数原理（加法/乘法原理）与组合数公式统计方案数。

思路框架（组合数学 通法 · 非本题专属）

  1. 判断是分类计数（相加）还是分步计数（相乘）。
  2. 识别是否重复/是否有序，决定用排列 A(n,m) 还是组合 C(n,m)。
  3. 组合数递推 C[i][j] = C[i-1][j-1] + C[i-1][j]，或预处理阶乘与逆元。
  4. 答案通常要求对 1e9+7 取模。

实现要点：阶乘预处理 + 费马小定理求逆元可以在 O(1) 内算任意组合数。

复杂度：时间 O(n) 预处理 / O(1) 查询 ｜ 空间 O(n)

该范式的通法易错点

  • 把排列和组合搞混。
  • 取模意义下直接做除法（应乘逆元）。

对照本题

  • 数据规模 t ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：2 / 2 2 / 3 3
  • 输出：2 / 9

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：贝壳找房2023届校招前端类试卷。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解