← 返回题目列表

Codeforces · 2239/D

D. 狩猎野兽

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

在浙江省中部城市诸暨,当地民间传说有一种野兽,被称为“ 模式。据说它栖息在深山中,夜间潜入村庄吞食牲畜并捕食孤独的旅行者。尽管许多长者声称见过它,但从未拍摄过该生物的照片。

一群勇敢的 $$$m$$$ 人决定上山猎杀野兽。山的位置和路径可以建模为 功能图 $$$G$$$ 具有 $$$n$$$ 顶点(编号为 $$$1$$$ 到 $$$n$$$)。函数图是具有 $$$n$$$ 个顶点和 $$$n$$$ 个边的有向图,其中每个顶点的出度恰好为 $$$1$$$。此外,众所周知,这座山的步道 永远不要形成自环.

该小组将精确选择$$$m$$$个不同的顶点来形成他们的初始起始集$$$S$$$。起始集合 $$$S$$$ 定义为 成功 如果图中的每个顶点 $$$u$$$ 都可以从至少一个顶点 $$$v \in S$$$ 到达(顶点始终可以从其自身到达)。

有 $$$\binom{n}{m}$$$ 可能的方法来选择大小 $$$m$$$ 的起始集。他们定义了 图表 $$$G$$$ 的 值 路径的 作为数量 成功 起始套装有。

然而,山上步道的确切布局尚不清楚。如果每个顶点的单个出边的目的地是从剩余的 $$$n-1$$$ 顶点(不包括顶点本身)中任意选择的,则恰好有 $$$(n-1)^n$$$ 可能的功能图。给定 $$$n$$$ 和 $$$m$$$,您的任务是计算所有 $$$(n-1)^n$$$ 可能的函数图的值之和。由于答案可能非常大,因此打印它对 $$$998\,244\,353$$$ 取模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n,m$$$ ($$$1\le m \le n\le 10^6$$$) — 图中的顶点数和起始顶点数。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出一个整数 - 所有 $$$(n-1)^n$$$ 可能的函数图的值的总和,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

5
2 1
3 1
3 2
4 2
8 3

输出
复制

2
12
18
216
20415360

注意

在第一个测试用例中,恰好存在 $$$(2-1)^2=1$$$ 有效函数图:$$$1 \to 2$$$ 和 $$$2 \to 1$$$。两个起始大小为 $$$1$$$ 的集合($$$\{1\}$$$ 和 $$$\{2\}$$$)都可以到达所有顶点。因此,总价值为$$$2$$$。

在第二个测试用例中,有 $$$(3-1)^3=8$$$ 有效函数图。它们可以分类如下:

  • $$$2$$$ 图形形成长度为 $$$3$$$ 的单个循环(例如,$$$1 \to 2 \to 3 \to 1$$$)。从 $$$3$$$ 中的任意一个顶点开始可以到达所有顶点。这将为总价值贡献$$$2 \cdot 3 = 6$$$。
  • $$$6$$$ 图由 $$$2$$$ 循环和指向它的单个叶子组成(例如,$$$1 \leftrightarrow 2$$$ 和 $$$3 \to 1$$$)。要到达所有顶点,起始集必须恰好是叶顶点。这将为总价值贡献 $$$6 \cdot 1 = 6$$$。
值的总和为 $$$6 + 6 = 12$$$。

在第三个测试用例中,$$$8$$$ 可能的图是相同的,但我们选择大小为 $$$m=2$$$ 的子集:

  • 对于 $$$2$$$ 循环图,大小为 $$$2$$$ 的任何子集都是成功的。这贡献了 $$$2 \cdot \binom{3}{2} = 6$$$。
  • 对于 $$$6$$$ 叶图,子集必须包含叶顶点。每个图恰好有 $$$\binom{2}{1}=2$$$ 这样的子集。这贡献了 $$$6 \cdot 2 = 12$$$。
值的总和为 $$$6 + 12 = 18$$$。