#P14077. [ICPC 2025 Jakarta R] Maximeter

    ID: 13284 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-树直径线性递推递归构造快速幂

[ICPC 2025 Jakarta R] Maximeter

题目描述

对于 TT 组测试数据,解决以下问题。

给定两个整数 MM 和 DD。你需要考虑一棵满足以下条件的带权有根树。

  • 每条边的权重均为正整数。
  • 对于树中的每个顶点 vv,不存在一个大小严格大于 MM 的 vv 的子节点集合,使得连接 vv 与该子节点集合中所有节点的边都具有相同的权重。
  • 树的直径不超过 DD。树的直径定义为任意两个顶点之间的最大距离。

求满足条件的树的最大顶点数。由于顶点数可能非常大,请输出顶点数对 998  244  353998\;244\;353 取模的结果。

输入格式

第一行包含一个整数 TT(1≤T≤1001 \leq T \leq 100),表示测试数据的组数。

接下来的 TT 行,每行包含两个整数 MM 和 DD(1≤M,D≤1091 \leq M, D \leq 10^9),表示一组需要求解的数据。

输出格式

对于每组测试数据,输出一行,包含最大顶点数对 998  244  353998\;244\;353 取模的结果。

输入输出样例 #1

输入 #1

3
2 4
165 1
20 20

输出 #1

12
2
891869870

说明/提示

样例 1 解释: 下图展示了第一组数据中顶点数最多的有根树。