304793: CF913H. Don't Exceed
Memory Limit:256 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Don't Exceed
题意翻译
# 题目描述 给定实数s1,s2,.....sn,满足以下要求: - s0=0; - si=si−1+ti,其中ti是在0~1之间随机一致选择的实数。 给定实数x1,x2,.....xn. 你需要找出所有符合条件Si<=xi的i值。 它可以表示为![](https://cdn.luogu.org/upload/vjudge_pic/CF913H/2c40be71c60fe708ee9e4e80e2cd7a26163f3bd6.png),其中P,Q互质;并且![](https://cdn.luogu.org/upload/vjudge_pic/CF913H/660186d645b69bba4bba5848de2ac09458cd0b37.png)。输出 P·Q^{-1}模998244353的值。 # 输入输出格式 输入格式: 第一行包含整数n(1<=n<=30). 接下来n行包含实数x1,x2,.....xn.保留6位小数(0 < xi ≤ n) 输出格式: 输出一个满足题意的解。 # 输入输出样例 ## 输入样例#1: 4 1.00 2 3.000000 4.0 ## 输出样例#1: 1 ## 输入样例#2: 1 0.50216 ## 输出样例#2: 342677322 ## 输入样例#3: 2 0.5 1.0 ## 输出样例#3: 623902721 ## 输入样例#4: 6 0.77 1.234567 2.1 1.890 2.9999 3.77 ## 输出样例#4: 859831967 # 说明 在输入样例#1中,所求的可以是1,因为不超过1的i实数之和不会超过i。 在输入样例#2中,可能是x1本身。 在输入样例#3中,所求的可以是 3/8。题目描述
You generate real numbers $ s_{1},s_{2},...,s_{n} $ as follows: - $ s_{0}=0 $ ; - $ s_{i}=s_{i-1}+t_{i} $ , where $ t_{i} $ is a real number chosen independently uniformly at random between 0 and 1, inclusive. You are given real numbers $ x_{1},x_{2},...,x_{n} $ . You are interested in the probability that $ s_{i}<=x_{i} $ is true for all $ i $ simultaneously. It can be shown that this can be represented as ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF913H/2c40be71c60fe708ee9e4e80e2cd7a26163f3bd6.png), where $ P $ and $ Q $ are coprime integers, and ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF913H/660186d645b69bba4bba5848de2ac09458cd0b37.png). Print the value of $ P·Q^{-1} $ modulo $ 998244353 $ .输入输出格式
输入格式
The first line contains integer $ n $ ( $ 1<=n<=30 $ ). The next $ n $ lines contain real numbers $ x_{1},x_{2},...,x_{n} $ , given with at most six digits after the decimal point ( $ 0<x_{i}<=n $ ).
输出格式
Print a single integer, the answer to the problem.
输入输出样例
输入样例 #1
4
1.00
2
3.000000
4.0
输出样例 #1
1
输入样例 #2
1
0.50216
输出样例 #2
342677322
输入样例 #3
2
0.5
1.0
输出样例 #3
623902721
输入样例 #4
6
0.77
1.234567
2.1
1.890
2.9999
3.77
输出样例 #4
859831967