H. Don't Exceed

Codeforces

IDCF913H

Time4000ms

Memory256MB

Difficulty—

mathprobabilities

English · Original

Chinese · Translation

Formal · Original

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. ## Input 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_). ## Output Print a single integer, the answer to the problem. [samples] ## Note 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.

你按如下方式生成实数序列 $[s_1, s_2, \dots, s_n]$：给定实数 $[x_1, x_2, \dots, x_n]$。你关心的是对所有 $i$ 同时满足 $s_i \le x_i$ 的概率。可以证明，该概率可以表示为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是互质的整数，且 $Q > 0$。请输出 $P \cdot Q^{-1}$ 对 $998244353$ 取模的值。第一行包含整数 $n$（$1 \le n \le 30$）。接下来 $n$ 行包含实数 $x_1, x_2, \dots, x_n$，小数点后最多六位数字（$0 < x_i \le n$）。输出一个整数，表示问题的答案。在第一个示例中，所求概率为 1，因为不超过 1 的 $i$ 个实数之和不会超过 $i$。在第二个示例中，概率就是 $x_1$ 本身。在第三个示例中，所求概率为 $3 / 8$。 ## Input 第一行包含整数 $n$（$1 \le n \le 30$）。接下来 $n$ 行包含实数 $x_1, x_2, \dots, x_n$，小数点后最多六位数字（$0 < x_i \le n$）。 ## Output 输出一个整数，表示问题的答案。 [samples] ## Note 在第一个示例中，所求概率为 1，因为不超过 1 的 $i$ 个实数之和不会超过 $i$。在第二个示例中，概率就是 $x_1$ 本身。在第三个示例中，所求概率为 $3 / 8$。

Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 30 $. Given real numbers $ x_1, x_2, \dots, x_n \in (0, n] $, each with at most six decimal digits. Let $ s_1, s_2, \dots, s_n $ be independent uniform random variables on $ [0,1] $. Define the event $ A = \bigcap_{i=1}^n \left\{ \sum_{j=1}^i s_j \leq x_i \right\} $. The probability $ \mathbb{P}(A) $ is a rational number $ \frac{P}{Q} $, where $ P, Q \in \mathbb{Z} $, $ \gcd(P, Q) = 1 $, $ Q > 0 $. Compute $ (P \cdot Q^{-1}) \mod 998244353 $, where $ Q^{-1} $ is the modular inverse of $ Q $ modulo $ 998244353 $.

Samples

Input #1

Output #1

Input #2

1
0.50216

Output #2

342677322

Input #3

2
0.5
1.0

Output #3

623902721

Input #4

Output #4

859831967

API Response (JSON)

{
  "problem": {
    "name": "H. Don't Exceed",
    "description": {
      "content": "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, i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF913H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You generate real numbers _s_1, _s_2, ..., _s__n_ as follows:\n\n*   _s_0 = 0;\n*   _s__i_ = _s__i_ - 1 + _t__i_, where _t__i_ is a real number chosen independently uniformly at random between 0 and 1, i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你按如下方式生成实数序列 $[s_1, s_2, \\dots, s_n]$：\n\n给定实数 $[x_1, x_2, \\dots, x_n]$。你关心的是对所有 $i$ 同时满足 $s_i \\le x_i$ 的概率。\n\n可以证明，该概率可以表示为 $\\frac{P}{Q}$，其中 $P$ 和 $Q$ 是互质的整数，且 $Q > 0$。请输出 $P \\cdot Q^{-1}$ 对 $998244353$...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 30 $.\n\nGiven real numbers $ x_1, x_2, \\dots, x_n \\in (0, n] $, each with at most six decimal digits.\n\nLet $ s_1, s_2, \\dots, s_n $ be independent uniform rand...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments