美团 · 组合数学 · 算法编程题
美团 组合数学 N ≤ 1e3 时限 1 秒 / 256 MB

题目描述

小团是旅店老板，现在有连续的N个房间（从左到右分别编号从1到N），每个房间可以住一个旅客。
有P个游客通过美团酒店业务来到小团的旅店住宿，小团的任务是想办法给他们分配房间，要求相邻的两个房间不可以同时住上旅客。（比如3号房间和4号房间相邻，你可以两个房间都不住人，也可以3号房间住一个人4号不住，也可以3号不住4号房间住一个人，但不可以3号和4号都住人）
对于无法找到合法的方案进行分配的情况，输出0即可。
方案数不对具体的游客进行区分。例如1号房间住旅客A，3号房间住旅客B，和1号房间住旅客B，3号房间住旅客A视为同一种方案，即分配了1号和3号房间。
你的任务是给出有多少种分配的方案，方案数对10000取模即可。
保证 0 < P < N

输入输出

输入描述
一行两个以空格分开的自然数N和P。
对于40%的数据有2 <= N <= 10
对于60%的数据有2 <= N <= 100
对于100%的数据有2 <= N <= 1000
输出描述
一行一个正整数表示分配的方案数量。

样例共 2 组

样例 1 · 对于样例1，只有一种分配方案，分配1号房间、三号房间、五号房间，也即（1，3，5）
输入
5 3
输出
1
样例 2 · 对于样例2，有四种分配方案，分别是（1，3，5），（1，3，6），（1，4，6），（2，4，6）
输入
6 3
输出
4

算法解析依据一般

考点：组合数学

数据规模 N ≤ 1e3 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 1e3
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：组合数学

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

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

  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)

该范式的通法易错点

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

对照本题

  • 数据规模 N ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 5 3 → 输出 1

对于样例1，只有一种分配方案，分配1号房间、三号房间、五号房间，也即（1，3，5）

样例 2：输入 6 3 → 输出 4

对于样例2，有四种分配方案，分别是（1，3，5），（1，3，6），（1，4，6），（2，4，6）

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

本题来源：美团2023校招笔试-编程题（算法编程题）。

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