首页 > 试题广场 >

take

[编程题]take

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

Kanade has n boxes , the i-th box has p[i] probability to have an diamond of d[i] size.

At the beginning , Kanade has a diamond of 0 size. She will open the boxes from 1-st to n-th. When she open a box,if there is a diamond in it and it's bigger than the diamond of her , she will replace it with her diamond.

Now you need to calculate the expect number of replacements.

You only need to output the answer module 998244353.

Notice: If x%998244353=y*d %998244353 ,then we denote that x/y%998244353 =d%998244353

输入描述:

The first line has one integer n.

Then there are n lines. each line has two integers p[i]*100 and d[i].

输出描述:

Output the answer module 998244353

示例1

输入

输出

499122178

备注:

1<= n <= 100000

1<=p[i]*100 <=100

1<=d[i]<=10^9

算法知识视频讲解

hrdate

发表于 2020-07-08 20:54:19

题意:有n个盒子，每个盒子有p概率使得盒子里面有一个大小为d的钻石，每次遇到遇到比你手中更大的钻石你需要进行交换。现在你可以从第1个盒子开始，一直任意选到第n个，求交换次数的期望值是多少。题解:每个盒子的概率p的乘100后的值，考虑到大数，就可以考虑用乘法逆元对于期望高中已学过E(X+Y)=E(X) 展开全文

阿哲不是吧

发表于 2020-10-06 17:21:57

take题解参考题目描述 Kanade has n boxes , the i-th box has p[i] probability to have andiamond of d[i] size. At the beginning , Kanade has a diamond of 0 siz 展开全文