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

题目描述

小团和小美正在玩一个填数游戏，这个游戏是给一个等式，其中有一些数被挖掉了，你需要向其中填数字，使得等式成立。
比如 ___+12=34，那么横线填的一定是22
现在，这个游戏到了最后一关，这一关的等式很奇特：_+_+_+...+_=n
这里可以填任意多个正整数（甚至可能是1个），只要这些数的和等于n即可。
但是，有一个额外的限制，填入的所有数必须小于等于k，大于等于1，填入的数的最大值必须大于等于d。
请你计算，有多少个不同的等式满足这些限制。由于答案可能很大，请将答案mod(998244353)后输出。

输入输出

输入描述
输入包含三个数n, k, d
输出描述
输出包含一行，即方案数。

样例共 1 组

样例 1 · 2+3=5 3+2=5 1+1+3=5 1+3+1=5 3+1+1=5 1+2+2=5 2+1+2=5 2+2+1=5 1+1+1+2=5 1+1+2+1=5 1+2+1+1=5 2+1+1+1=5 共12种填法
输入
5 3 2
输出
12

算法解析依据一般

考点：组合数学

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 源站时限：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)

该范式的通法易错点

  • 把排列和组合搞混。
  • 取模意义下直接做除法（应乘逆元）。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

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

2+3=5

3+2=5

1+1+3=5

1+3+1=5

3+1+1=5

1+2+2=5

2+1+2=5

2+2+1=5

1+1+1+2=5

1+1+2+1=5

1+2+1+1=5

2+1+1+1=5

共12种填法

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

本题来源：美团2023校招技术第6场编程题。

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