笔试时间：2025年8月17日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：无人机飞行路径探索

在实际的无人机物流配送场景中，某配送区域被划分为 m 行 n 列的网格状飞行单元，每个单元格代表一个标准飞行区域（如100米×100米的安全飞行范围）。无人机从位于左上角的起始仓库出发，需要将货物送达右下角的配送点。为避免频繁转向影响飞行效率和避障系统稳定性，无人机每次只能执行两种基础飞行动作：向右平移一个单元格（对应飞行方向向东）或向下平移一个单元格（对应飞行方向向南）。请问，无人机从起始仓库到配送点共有多少种不同的可行飞行路径？

输入描述

输入为两行，每行一个正整数，分别代表配送区域m行n列

输出描述

输出为正整数

样例输入

3

7

样例输出

28

提示：m>0，m<=200 n>0，n<=200

参考题解

这是一个经典的组合数学问题。 题目要求从一个 m 行 n 列的网格的左上角走到右下角，每次只能向右或向下移动。为了到达终点，无人机总共需要向右移动 n-1 次，向下移动 m-1 次。总移动次数为 (m-1) + (n-1) = m + n - 2。 问题等价于：在总共 m + n - 2 次移动中，选择 n - 1 次向右移动（或者选择 m-1 次向下移动）。 这可以用组合公式 C(total_steps, right_moves) 来计算。 C(k, r) = k! / (r! * (k-r)!) 在此问题中: total_steps = m + n - 2 right_moves = n - 1 优化的计算方法，避免直接计算大阶乘，以防止数值溢出和提高效率。 C(n, k) = (n * (n-1) * ... * (n-k+1)) / k! 为了减少循环次数，我们可以选择较小的组合数。 C(n, k) = C(n, n-k) 这里的 k 是 min(right_moves, total_steps - right_moves)

C++：

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;

// 计算 C(total, r)
cpp_int comb(long long total, long long r) {
    long long k = min(r, total - r);
    cpp_int res = 1;
    for (long long i = 0; i < k; ++i) {
        res *= (total - i);
        res /= (i + 1);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);