← 返回题目列表

Codeforces · 1156/F

F. 卡包

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

你有一个包,里面装着 $$$n$$$ 卡。每张卡上都写有一个号码;第 $$$i$$$ 卡上的号码是 $$$a_i$$$。

您正在玩以下游戏。在每个回合中,您选择并从袋子中随机取出一张卡片(仍然留在袋子内的所有卡片都会被同等地选择)。在第一回合中没有发生任何其他事情 - 但在接下来的回合中,在移除一张卡后(令其上的数字为 $$$x$$$),您将其与上一回合中移除的卡进行比较(令其上的数字为 $$$y$$$)。可能的结果是:

- 如果 $$$x < y$$$,游戏结束,你输;
- 如果 $$$x = y$$$,游戏结束,你获胜;
- 如果 $$$x > y$$$,游戏继续。

如果袋子里没有牌了,你就输了。取出卡片后,卡片不会放回包中。

你必须计算在这场游戏中获胜的概率。可以证明其形式为$$$\frac{P}{Q}$$$,其中$$$P$$$和$$$Q$$$为非负整数,$$$Q \neq 0$$$, $$$P \le Q$$$。输出 $$$P \cdot Q^{−1} ~(mod ~~ 998244353)$$$ 的值。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5000$$$) — 袋子中的卡片数量。

第二个 live 包含 $$$n$$$ 整数 $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le n$$$) — 第 $$$i$$$ 个整数是写在第 $$$i$$$ 卡上的数字。

输出

打印一个整数 — 在这场游戏中获胜的概率以 $$$998244353$$$ 为模。

示例

输入 #1

5
1 1 4 2 3

输出 #1

299473306

输入 #2

2
2 2

输出 #2

1

输入 #3

5
4 5 1 3 2

输出 #3

0

输入#4

4
1 3 4 3

输出#4

748683265

注意

在第一个测试用例中,获胜的概率为 $$$\frac{1}{10}$$$。

在第二个测试用例中,获胜的概率为 $$$1$$$。

在第三个测试用例中,获胜的概率为 $$$0$$$。

在第四个测试用例中,获胜的概率为 $$$\frac{1}{4}$$$。