TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

60.0% (6/10)

Tags

Description

就像其他的物種一樣,人類也有很多進化方向
人類如果往「魔素量增加」的方向修煉的話,會進化成「魔人」,「魔人」只要收集1萬個靈魂就能進化成「魔王」,「魔王」如果收集到7個大罪系的究極能力就能進化成「惡魔」
與其不同,人類如果往「技術強化」的方向修煉的話,會進化成「仙人」,「仙人」只要將自身的細胞融合就能進化成「聖人」,「聖人」如果收集到7個美德系的究極能力就能進化成「天使」
奇妙的是,這個世界有一個超規格的存在:「天神」,無論是哪個種族,如果收集到7個大罪系的究極能力+7個美德系的究極能力就能進化成「天神」,特別的是本來只要獲得3個究極能力就有權限遮蔽「世界之聲」,但是進化成「天神」的通知無法以任何方式遮蔽。
就在某一天,世界之聲發出通知了:「確認,個體名:『天使』------收集到『暴食之王 別西卜』、『傲慢之王 路西法』、『憤怒之王 撒旦』、『嫉妒之王 利維坦』、『怠惰之王 貝爾菲戈爾』、『色慾之王 阿斯蒙蒂斯』、『貪婪之王 瑪門』7 種大罪系能力以及『正義之王 米迦勒』、『救恤之王 拉貴爾』、『忍耐之王 加百列』、『智慧之王 拉斐爾』、『希望之王 沙利葉』、『純潔之王 梅塔特隆』、『誓約之王 烏列爾』7種美德系能力,往『天神』進化」
雖然最重要的個體名稱被干擾了,可是這則通知依然成為了天使間的頭條新聞,為了找尋茫茫天使海中誰是天神,加百列開發出了一種被稱為「天神偵測魔法」的術式,這個術式由k個法陣組成,每個法陣可以站任意多位天使,發動術式之後天神所在的法陣就會發亮
不過由於發動術式需要大量的魔力,加百列先偷偷調查了每個天使的某些特質(會不會寫treap等等),列出每個天使是天神的期望值,現在加百列想要知道,他發動術式的次數期望值是多少?

Input Format

第一行有兩個用空白隔開的正整數$n,k(1\leq k<n\leq 10^ 6)$,代表天使的數量及一個天神偵測魔法術式的法陣數量
第二行有$n$個正整數$p_i(1\leq i\leq n,1\leq p_i\leq 10^ 8)$,表示第$i$個天使是天神的機率是$\frac{p_i}{\sum\limits^ {n}_{j=1}p_j}(1\leq i\leq n)$

Output Format

若發動術式次數的期望值是$\alpha$,可以證明 $\alpha\times \sum\limits^ {n}_ {i=1}p_ i$ 是整數。
請輸出 $\alpha\times \sum\limits^ {n}_ {i=1}p_ i$。

Sample Input

6 2
5 6 7 8 9 10

Sample Output

80

Hints

子任務(測資)額外限制分數
1(0~4)$n\leq 10$10
2(0~9)$n\leq 10000$10
3(0~14)$n\leq 2\times 10^5$20
4(0~19)$n\leq 10^6$60

在Sample Input中,最佳策略是:
(1)先將{1號天使,2號天使}和{6號天使}放入法陣
(2.1)若沒有找到,將{3號天使}和{4號天使}放入法陣
(2.2)若天神在{1號天使,2號天使},則將{1號天使}和{2號天使}放入法陣
這樣的期望值是$\frac{16}{9}$

Problem Source

Problem set and Description by Double

Subtasks

For Testdata: 0 ~ 4, Score: 10
For Testdata: 0 ~ 9, Score: 10
For Testdata: 0 ~ 14, Score: 20
For Testdata: 0 ~ 29, Score: 60
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536
20 1000 65536 65536
21 1000 65536 65536
22 1000 65536 65536
23 1000 65536 65536
24 1000 65536 65536
25 1000 65536 65536
26 1000 65536 65536
27 1000 65536 65536
28 1000 65536 65536
29 1000 65536 65536