#P6912. 小球

    ID: 6743 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 5 上传者: 标签>难度分类普及+/提高-排序与序列处理二分答案组合数学组合数乘法递推CF1800

小球

小球

题目描述

小 C 有 mm 个性能完全相同的小球和一个发射器。发射器可以把一个小球以任意不超过最高速度 nn 的正整数速度发射出去,直到撞墙。

小球在速度 00 时一定不会碎。如果某速度会使小球碎裂,则更高速度也会使它碎裂;如果某速度不会使小球碎裂,则更低速度也不会。

小球的性能定义为刚好会使其碎裂的最小正整数速度 vv。若以最高速度 nn 发射仍不会碎,则定义其性能为 n+1n+1。

小球在碎裂前可以反复发射,碎裂后便不能再使用。每次可以根据之前的发射结果,决定下一次的发射速度。

求保证能够确定性能时,在最坏情况下至少需要启动发射器多少次。

输入格式

一行两个正整数 n,mn,m,分别表示最高速度和小球数量。

输出格式

输出一个整数,表示最少启动次数对 998244353998244353 取模的结果。

样例输入

5 2

样例输出

3

数据范围

1≤n,m≤1061\le n,m\le10^6。

子任务 分值 特殊限制
11 n,m≤100n,m\le100
22 1515 n,m≤400n,m\le400
33 88 n,m≤1000n,m\le1000
44 3232 n,m≤2×105n,m\le2\times10^5
55 11 m=1m=1
66 22 m=2m=2
77 4141 无