D. New Year and Arbitrary Arrangement

Codeforces

IDCF908D

Time2000ms

Memory256MB

Difficulty—

dpmathprobabilities

English · Original

Chinese · Translation

Formal · Original

You are given three integers _k_, _p__a_ and _p__b_. You will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With probability _p__a_ / (_p__a_ + _p__b_), add '_a_' to the end of the sequence. Otherwise (with probability _p__b_ / (_p__a_ + _p__b_)), add '_b_' to the end of the sequence. You stop once there are at least _k_ subsequences that form '_ab_'. Determine the expected number of times '_ab_' is a subsequence in the resulting sequence. It can be shown that this can be represented by _P_ / _Q_, where _P_ and _Q_ are coprime integers, and . Print the value of . ## Input The first line will contain three integers integer _k_, _p__a_, _p__b_ (1 ≤ _k_ ≤ 1 000, 1 ≤ _p__a_, _p__b_ ≤ 1 000 000). ## Output Print a single integer, the answer to the problem. [samples] ## Note The first sample, we will keep appending to our sequence until we get the subsequence '_ab_' at least once. For instance, we get the sequence '_ab_' with probability 1/4, '_bbab_' with probability 1/16, and '_aab_' with probability 1/8. Note, it's impossible for us to end with a sequence like '_aabab_', since we would have stopped our algorithm once we had the prefix '_aab_'. The expected amount of times that '_ab_' will occur across all valid sequences is 2. For the second sample, the answer is equal to .

你被给定三个整数 $k$、$pa$ 和 $pb$。你将使用以下算法构造一个序列：初始时序列为空。每一秒，你执行以下操作：以概率 $pa/(pa+pb)$，在序列末尾添加 '_a_'；否则（概率为 $pb/(pa+pb)$），在序列末尾添加 '_b_'。当你至少获得了 $k$ 个构成 '_ab_' 的子序列时，停止构造。求最终序列中 '_ab_' 作为子序列出现次数的期望值。可以证明，该期望值可以表示为 $P/Q$，其中 $P$ 和 $Q$ 是互质的整数，且 $Q \not\equiv 0 \pmod{998244353}$。请输出 $P \cdot Q^{-1} \bmod 998244353$ 的值。第一行包含三个整数 $k, pa, pb$（$1 \leq k \leq 1\,000$，$1 \leq pa, pb \leq 1\,000\,000$）。输出一个整数，表示问题的答案。在第一个样例中，我们将持续向序列追加字符，直到至少出现一次 '_ab_' 子序列。例如，我们以概率 $1/4$ 得到序列 '_ab_'，以概率 $1/16$ 得到 '_bbab_'，以概率 $1/8$ 得到 '_aab_'。注意，我们不可能得到类似 '_aabab_' 的序列，因为一旦我们有了前缀 '_aab_'，算法就已经停止了。在所有合法序列中，'_ab_' 作为子序列出现次数的期望值为 2。在第二个样例中，答案等于。 ## Input 第一行包含三个整数 $k, pa, pb$（$1 \leq k \leq 1\,000$，$1 \leq pa, pb \leq 1\,000\,000$）。 ## Output 输出一个整数，表示问题的答案。 [samples] ## Note 在第一个样例中，我们将持续向序列追加字符，直到至少出现一次 '_ab_' 子序列。例如，我们以概率 $1/4$ 得到序列 '_ab_'，以概率 $1/16$ 得到 '_bbab_'，以概率 $1/8$ 得到 '_aab_'。注意，我们不可能得到类似 '_aabab_' 的序列，因为一旦我们有了前缀 '_aab_'，算法就已经停止了。在所有合法序列中，'_ab_' 作为子序列出现次数的期望值为 2。在第二个样例中，答案等于。

**Definitions** Let $ k, p_a, p_b \in \mathbb{Z}^+ $ be given integers. Let $ P = \frac{p_a}{p_a + p_b} $, $ Q = \frac{p_b}{p_a + p_b} $ be the probabilities of appending 'a' and 'b', respectively. **Constraints** $ 1 \leq k \leq 1000 $, $ 1 \leq p_a, p_b \leq 10^6 $ **Objective** Let $ E(k) $ denote the expected number of subsequences "ab" in the random sequence generated by the process, stopping when the count of "ab" subsequences reaches at least $ k $. Compute $ E(k) $, and output the value of $ P \cdot Q^{-1} \mod (10^9 + 7) $, where $ E(k) = \frac{P}{Q} $ in reduced form.

Samples

Input #1

1 1 1

Output #1

Input #2

3 1 4

Output #2

370000006

API Response (JSON)

{
  "problem": {
    "name": "D. New Year and Arbitrary Arrangement",
    "description": {
      "content": "You are given three integers _k_, _p__a_ and _p__b_. You will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With prob",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF908D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given three integers _k_, _p__a_ and _p__b_.\n\nYou will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With prob...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定三个整数 $k$、$pa$ 和 $pb$。\n\n你将使用以下算法构造一个序列：初始时序列为空。每一秒，你执行以下操作：以概率 $pa/(pa+pb)$，在序列末尾添加 '_a_'；否则（概率为 $pb/(pa+pb)$），在序列末尾添加 '_b_'。\n\n当你至少获得了 $k$ 个构成 '_ab_' 的子序列时，停止构造。求最终序列中 '_ab_' 作为子序列出现次数的期望值。可以证明，该期望...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k, p_a, p_b \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ P = \\frac{p_a}{p_a + p_b} $, $ Q = \\frac{p_b}{p_a + p_b} $ be the probabilities of appending 'a' and 'b', respectively...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments