最小生成樹 - Problem

#10523. 最小生成樹

Statistics

AI Translation — This statement was translated using AI and may contain inaccuracies. Please refer to the original statement if in doubt.

所有邊排序

並查集尋找祖先

不同就合併

——最小生

——炸雞塊君

給定整數 $n, k$，求有多少種不同的 $n$ 個節點的無向連通圖滿足：

圖中沒有自環，且任意兩個點之間至多有一條邊。
所有邊的邊權為 $[1, k]$ 之間的整數。
對於圖中的每條邊，都至少存在一棵最小生成樹包含該邊。

兩張圖不同當且僅當存在一對節點 $(u, v)$，使得一張圖中 $u, v$ 之間有邊而另一張沒有，或是兩圖中 $u, v$ 之間的邊權不同。

請計算滿足條件的圖的數量，對 $998244353$ 取模。

輸入格式

每個測試文件僅有一組測試數據。

第一行包含兩個正整數 $n$ 和 $k$ ($1 \le n \le 5 \times 10^4, 1 \le k \le 10$)。

輸出格式

一行一個整數，表示答案對 $998244353$ 取模的結果。

範例

輸入 1

3 1

輸出 1

輸入 2

4 2

輸出 2

輸入 3

235 7

輸出 3

928998036

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0

No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
Do not submit duplicated issues.
Issues must be filed in English or Chinese only.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0