← 返回题目列表

Codeforces · 1912/B

B. 座位蓝图

中文机器翻译题面 查看原题

一家飞机制造公司希望为客运航空公司优化其产品。该公司的最新研究显示,大部分延误是由于登机速度慢造成的。

中型飞机大多采用3-3座布局设计,即每排有6个座位:左侧3个座位,单通道,右侧3个座位。左右两侧各有一个靠窗的座位、一个中间的座位和一个靠过道的座位。即使飞机上没有其他人,登上分配到过道座位的乘客所花费的时间也比分配到靠窗座位的乘客要少得多。

公司决定计算 不便 布局的 为单排每个座位到最近过道的距离总和。座位到过道的距离是它们之间的座位数。对于 3-3 布局,靠窗座位的距离为 2,中间座位 - 1,过道座位 - 0。3-3 布局的不便之处在于 $$$(2+1+0)+(0+1+2)=6$$$。 3-5-3布局的不便之处在于$$$(2+1+0)+(0+1+2+1+0)+(0+1+2)=10$$$。

形式上,布局是正整数的序列 $$$a_1, a_2, \ldots, a_{k+1}$$$ — 组 $$$i$$$ 拥有 $$$a_i$$$ 座位,组之间有 $$$k$$$ 过道,第 $$$i$$$ 过道位于组 $$$i$$$ 和 $$$i$$$ 之间$$$i+1$$$。这意味着在布局中,每条过道必须始终位于两个座位之间,因此过道不能紧邻窗户,也不能有两个过道彼此相邻。

公司决定设计一种布局,其中包含一排 $$$n$$$ 座位、$$$k$$$ 过道,并尽可能减少不便。帮助他们找到 $$$n$$$ 座位和 $$$k$$$ 过道的所有布局中最小的不便,并以 $$$998\,244\,353$$$ 为模计算此类布局的数量。

输入

第一行包含一个整数 $$$t$$$ — 您需要解决的测试用例数量 ($$$1 \le t \le 10^5$$$)。

对于每个测试用例,都有一行包含 $$$n$$$ 和 $$$k$$$ — 座位数和一行中的过道数 ($$$2 \le n \le 10^9$$$; $$$1 \le k \le 10^5$$$; $$$k \lt n$$$)。

给定测试用例中所有 $$$t$$$ 的 $$$k$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,打印两个整数 - 所有可能布局中的最小不便性,以及最小不便性模 $$$998\,244\,353$$$ 的布局数量。

示例

输入
复制

8
4 1
3 2
4 2
5 2
6 1
6 2
1000000000 1
9 2

输出
复制

2 1
0 1
0 1
1 3
6 1
2 4
249999999500000000 1
6 3

注意

在最后一个测试用例中 9 2 不便程度最小为 6 的可能布局是 3-4-2、2-4-3 和 2-5-2。