# 20180706 模拟赛 T3 -- 神经衰弱 Author: Fanyi Pu Published: 2018-09-08 Canonical: 20180706 模拟赛 T3 -- 神经衰弱 > **文件名：** card **题目类型：** 传统题 **时间限制：** 1 秒 **内存限制：** 128 MB **编译优化**： 无 ### 题目描述 天然少女小雪非常喜欢玩一个叫做神经衰弱的游戏。 游戏规则是，有若干种牌，每种牌有若干对，开始时全都正面朝下放置。 然后每次同时翻开两张牌，假如这两张牌是同一种类，则拿走这两张牌，否则再次翻回背面。 小雪虽然看上去傻乎乎的但是玩这个游戏非常厉害，所以可以认为她是绝对聪明的，即会采取最优决策和有着完美的记忆力。 现在小雪想要知道，对于某一副牌局，她期望拿多少次可以拿走所有牌。 需要注意的是小雪玩的神经衰弱和普通神经衰弱有所不同。普通神经衰弱是依次拿走两张牌，而小雪的神经衰弱是同时拿走两张牌。 #### 输入格式 第一行一个整数 $n$ 表示牌的种类数 第二行 $n$ 个整数 $a_{i}$ 表示第 $i$ 种牌有多少对 #### 输出格式 一个整数，表示期望 $\mod998244353$ 即假如答案是 $\frac{a}{b}$, 你需要输出的是某个数 $x$，使 $xb=a\pmod {998244353}$ 保证 $a\not=0,b\not=0$ #### 样例输入 > 2 > > 1 1 #### 样例输出 > 332748121 ### 数据规模与约定 30%: $n≤5,a_{i}≤2$ 60%: $n≤3000$ 对于所有数据 $n≤10^6,a_{i}≤10^9$ ## 题解 首先，发现两张牌相同后不管什么时间把它们拿去都是一样的，所以我们统一最后拿去。 我们设 $s$ 为总对数，即 $s = \sum_{i=1}^{n}a_i$。 则总共有 $2s$ 张牌。 那如果抽出的两张牌都两两不同，则总和为须 $s$ 次。 然后我们把它们一个个拿去，又须 $s$ 次。 所以总共 $2s$ 次。 然而可能有情况一次性抽到了两张相同的牌，所以我们要把它的期望减去。 首先，对于任意 $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}$。