A11515. Don't Exceed
编程题
普及/提高-
知识点
题目描述
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 , where $P$ and $Q$ are coprime integers, and . Print the value of $P·Q^{-1}$ modulo $998244353$ .
- $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 , where $P$ and $Q$ are coprime integers, and . 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$ ).
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
说明/提示
In the first example, the sought probability is 1 since the sum of $i$ real numbers which don't exceed 1 doesn't exceed $i$ .
In the second example, the probability is $x_{1}$ itself.
In the third example, the sought probability is $3/8$ .
In the second example, the probability is $x_{1}$ itself.
In the third example, the sought probability is $3/8$ .