AT_abc386_g.[ABC386G] Many MST

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定两个正整数 $N$ 和 $M$ 。我们考虑一个有 $N$ 个顶点的完全图，顶点编号从 $1$ 到 $N$ 。在这个图中，每条边的权重是从 $1$ 到 $M$ 的整数。对于这种图，共存在 $M^{N(N-1)/2}$ 种不同的可能性。对于每种可能的图，我们要计算出它的最小生成树中所有边的权重之和。最后，我们需要计算这些权重和的总和，并输出该总和对 $998244353$ 取模的结果。

输入格式

输入包含两个整数 $N$ 和 $M$ 。

输出格式

输出一个整数，表示所有图的最小生成树的权重和的总和对 $998244353$ 取模的结果。

输入输出样例

输入#1
```
3 2
```
输出#1
```
21
```
输入#2
```
2 100
```
输出#2
```
5050
```
输入#3
```
20 24
```
输出#3
```
707081320
```

说明/提示

$2 \leq N \leq 500$
$1 \leq M \leq 500$
所有输入值均为整数

示例解释

如果一个三顶点的完全图，其边的权重是 $1$ 或 $2$ ，有 $8$ 种可能的图。每个图的最小生成树中的边权重和为 $2, 2, 2, 3, 2, 3, 3, 4$ ，因此答案是 $21$ ，即 $2 + 2 + 2 + 3 + 2 + 3 + 3 + 4 = 21$ 。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页