小团正在装饰自己的书桌,他的书桌上从左到右有m个空位需要放上装饰物。商店中每个整数价格的装饰物恰好有一种,且每种装饰物的数量无限多。 小团去商店的时候,想到了一个购买方案,他要让右边的装饰物价格是左边的倍数。用数学语言来说,假设小团的m个装饰物价格为 a_1,a_2,...,a_m ,那么对于任意的1≤i≤j≤m, a_j 是 a_i 的倍数。 小团是一个节约的人,他希望最贵的装饰物不超过n元。现在,请你计算小团有多少种购买的方案?
输入包含两个数,n和m
输出一个数,结果对998244353取模,表示购买的方案数。
4 2
8
考点:组合数学
限制 1 秒 / 256MB | 标准输入输出
参考方向:组合数学
用计数原理(加法/乘法原理)与组合数公式统计方案数。
思路框架(组合数学 通法 · 非本题专属)
实现要点:阶乘预处理 + 费马小定理求逆元可以在 O(1) 内算任意组合数。
复杂度:时间 O(n) 预处理 / O(1) 查询 | 空间 O(n)
该范式的通法易错点
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1:输入 4 2 → 输出 8
[1,1][1,2][1,3][1,4][2,2][2,4][3,3][4,4]共8种
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:美团2023校招笔试-编程题(算法编程题)。