20180706 模拟赛 T3 -- 神经衰弱

文件名： card 题目类型： 传统题 时间限制： 1 秒 内存限制： 128 MB 编译优化：无

天然少女小雪非常喜欢玩一个叫做神经衰弱的游戏。

游戏规则是，有若干种牌，每种牌有若干对，开始时全都正面朝下放置。

然后每次同时翻开两张牌，假如这两张牌是同一种类，则拿走这两张牌，否则再次翻回背面。

小雪虽然看上去傻乎乎的但是玩这个游戏非常厉害，所以可以认为她是绝对聪明的，即会采取最优决策和有着完美的记忆力。

现在小雪想要知道，对于某一副牌局，她期望拿多少次可以拿走所有牌。

需要注意的是小雪玩的神经衰弱和普通神经衰弱有所不同。普通神经衰弱是依次拿走两张牌，而小雪的神经衰弱是同时拿走两张牌。

第一行一个整数 $n$ 表示牌的种类数

第二行 $n$ 个整数 $a_{i}$ 表示第 $i$ 种牌有多少对

一个整数，表示期望 $\mod 998244353$

即假如答案是 $\frac{a}{b}$ , 你需要输出的是某个数 $x$ ，使 $x b = a (\mod 998244353)$

保证 $a \neq 0, b \neq 0$

2

1 1

332748121

30%: $n \leq 5, a_{i} \leq 2$

60%: $n \leq 3000$

对于所有数据 $n \leq 10^{6}, a_{i} \leq 10^{9}$

题解

首先，发现两张牌相同后不管什么时间把它们拿去都是一样的，所以我们统一最后拿去。

我们设 $s$ 为总对数，即 $s = \sum_{i = 1}^{n} a_{i}$ 。

则总共有 $2 s$ 张牌。

那如果抽出的两张牌都两两不同，则总和为须 $s$ 次。

然后我们把它们一个个拿去，又须 $s$ 次。

所以总共 $2 s$ 次。

然而可能有情况一次性抽到了两张相同的牌，所以我们要把它的期望减去。

首先，对于任意 $i$ 其发生的概率为 $\frac{C_{a_{i}}^{2}}{C_{s}^{2}}$ ，化简一下，得到 $\frac{a_{i} (a_{i} - 1)}{s (s - 1)}$ 。

所以总概率为 $\sum_{i = 1}^{n} \frac{a_{i} (a_{i} - 1)}{s (s - 1)} = \frac{\sum_{i = 1}^{n} a_{i} (a_{i} - 1)}{s (s - 1)}$ 。

总共选 $s$ 次，所以期望为 $s \times \frac{\sum_{i = 1}^{n} a_{i} (a_{i} - 1)}{s (s - 1)} = \frac{\sum_{i = 1}^{n} a_{i} (a_{i} - 1)}{s - 1}$ 。