#6267. 生成随机数

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Moiezen

题目描述

「诶,我想生成一个随机数,等概率是 1 2 。」

「呐,我给你一枚均匀的硬币,你扔一次就好啦。」

「那如果我想让它等概率是 1 2 3 呢?」

「嗯,我想想。这样吧,你先扔两次,如果依次是反反就生成 1 ,反正就生成 2 ,正反就生成 3 ,正正就重新来吧。」

「诶,这个方案是不是有可能永远不能结束啊?」

「是的呢,但是期望 \frac{8}{3} 次就可以结束了,而且这是期望次数最小的方案。」

「好厉害呀。那如果我还是想让它是 1 2 ,但是概率比是 1 2 呢?」

「还是可以用刚才的方案,如果生成了 3 就当成 2 好了。」

「啊,那在这里还是期望次数最小的方案吗?」

「应该不是了吧,毕竟浪费了一些信息。」

「那么应该是什么方案呢?」

「似乎有点复杂了呢,让我想一想。」

从前有一个随机数生成器,能够生成一个 [1,n] 内的整数,且生成 i 的权重是 a_i (即生成 1\ldots n 的概率比是 a_1:a_2:\ldots :a_n )。现在它已经找不到了,而你想模拟这个生成的过程,但是你手里只有一枚均匀的硬币。你想了很久,设计了一个方案并开始扔硬币。可是你扔了很多很多次硬币,却发现你还是没有模拟成功——或许这个方案实在太慢了,甚至有可能永远不会结束。于是你希望找到一个期望扔硬币次数最少的模拟方案,但是这个方案讲起来可能比较复杂,你想先知道这个最少的期望扔硬币次数。

输入格式

第一行,一个正整数 n

第二行, n 个空格隔开的正整数,其中第 i 个数是 a_i

输出格式

我们保证这个答案是一个正有理数,设其等于 \frac{P}{Q} ,且 P Q 是互质的正整数。

我们保证存在非负整数 R ,使得 P R\times Q 998244353 取余的结果相等,设 S 是最小的 R

仅一行,一个非负整数 S

样例

样例输入 1

2
1 1

样例输出 1

1

样例说明 1

P=1,Q=1 ,方案见题目背景。

样例输入 2

3
1 1 1

样例输出 2

665496238

样例说明 2

P=8,Q=3 ,方案见题目背景。

样例输入 3

2
1 3

样例输出 3

499122178

样例说明 3

P=3,Q=2 ,方案是如果第一次正面则直接生成 2 ,否则根据第二次来生成 1 2

样例输入 4

7
1 1 1 1 1 1 1

样例输出 4

570425348

样例说明 4

P=24,Q=7 ,方案略。

样例输入 5

3
2 3 3

样例输出 5

748683267

样例说明 5

P=9,Q=4 ,方案略。

样例输入 6

3
1 3 5

样例输出 6

887328316

样例说明 6

P=20,Q=9 ,方案略。

样例输入 7

3
3 3 4

样例输出 7

798595485

样例说明 7

P=13,Q=5 ,方案略。

数据范围与提示

测试点编号 规模限制 特殊限制
1 n=2 A
2,3 B
4
5 n=m A
6,7 B
8
9 m\le 10^3 A
10,11 B
12
13 m\le 10^5 A
14,15 B
16
17 A
18,19 B
20

对于所有数据, n\leq 10^6 m\leq 10^7 。其中 m 表示所有 a_i 的和,A 表示 m 2 的幂次,B 表示 m 是奇数。