F. Strongly Connected Tournament

Codeforces

IDCF913F

Time2000ms

Memory256MB

Difficulty—

dpgraphsmathprobabilities

English · Original

Chinese · Translation

Formal · Original

There is a chess tournament in All-Right-City. _n_ players were invited to take part in the competition. The tournament is held by the following rules: 1. Initially, each player plays one game with every other player. There are no ties; 2. After that, the organizers build a complete directed graph with players as vertices. For every pair of players there is exactly one directed edge between them: the winner of their game is the startpoint of this edge and the loser is the endpoint; 3. After that, the organizers build a condensation of this graph. The condensation of this graph is an acyclic complete graph, therefore it has the only Hamiltonian path which consists of strongly connected components of initial graph _A_1 → _A_2 → ... → _A__k_. 4. The players from the first component _A_1 are placed on the first places, the players from the component _A_2 are placed on the next places, and so on. 5. To determine exact place of each player in a strongly connected component, all the procedures from 1 to 5 are repeated recursively inside each component, i.e. for every _i_ = 1, 2, ..., _k_ players from the component _A__i_ play games with each other again, and so on; 6. If a component consists of a single player, then he has no more rivals, his place is already determined and the process stops. The players are enumerated with integers from 1 to _n_. The enumeration was made using results of a previous tournament. It is known that player _i_ wins player _j_ (_i_ < _j_) with probability _p_. You need to help to organize the tournament. Find the expected value of total number of games played by all the players. It can be shown that the answer can be represented as , where _P_ and _Q_ are coprime integers and . Print the value of _P_·_Q_ - 1 modulo 998244353. If you are not familiar with any of the terms above, you can read about them [here](https://en.wikipedia.org/wiki/Strongly_connected_component). ## Input The first line of input contains a single integer _n_ (2 ≤ _n_ ≤ 2000) — the number of players. The second line contains two integers _a_ and _b_ (1 ≤ _a_ < _b_ ≤ 100) — the numerator and the denominator of fraction . ## Output In the only line print the expected value of total number of games played by all the players. Print the answer using the format above. [samples] ## Note In the first example the expected value is 4. In the second example the expected value is . In the third example the expected value is .

在 All-Right-City 举办一场国际象棋锦标赛。共有 #cf_span[n] 名选手受邀参赛。比赛按以下规则进行：选手用从 #cf_span[1] 到 #cf_span[n] 的整数编号，编号是根据上一届比赛的结果确定的。已知选手 #cf_span[i] 击败选手 #cf_span[j]（#cf_span[i < j]）的概率为 #cf_span[p]。你需要协助组织这场比赛。求所有选手参加比赛的总场数的期望值。可以证明，答案可以表示为，其中 #cf_span[P] 和 #cf_span[Q] 是互质的整数，且。请输出 #cf_span[P·Q - 1] 对 #cf_span[998244353] 取模的值。如果你不熟悉上述任何术语，可以在这里阅读相关说明。输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 2000]）——选手人数。第二行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a < b ≤ 100]）——分数 #cf_span[p] 的分子和分母。仅输出一行，打印所有选手参加比赛的总场数的期望值。请按上述格式输出答案。在第一个示例中，期望值为 #cf_span[4]。在第二个示例中，期望值为。在第三个示例中，期望值为。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 2000]）——选手人数。第二行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a < b ≤ 100]）——分数 #cf_span[p] 的分子和分母。 ## Output 仅输出一行，打印所有选手参加比赛的总场数的期望值。请按上述格式输出答案。 [samples] ## Note 在第一个示例中，期望值为 #cf_span[4]。在第二个示例中，期望值为。在第三个示例中，期望值为。

Let $ n $ be the number of players, enumerated $ 1 $ to $ n $, where player $ i $ beats player $ j $ with probability $ p = \frac{a}{b} $ for all $ i < j $. The tournament is a single-elimination bracket: each game eliminates one player, and the tournament ends when one player remains. Thus, exactly $ n - 1 $ games are played in total, regardless of outcomes. Therefore, the total number of games played by all players is always $ n - 1 $, and its expectation is: $$ \mathbb{E}[\text{total games}] = n - 1 $$ This is a deterministic quantity — the structure of single-elimination tournaments fixes the number of games. We are to output $ P \cdot Q^{-1} \mod 998244353 $, where $ \frac{P}{Q} = n - 1 $, and $ \gcd(P, Q) = 1 $. So $ P = n - 1 $, $ Q = 1 $, and the answer is: $$ (n - 1) \cdot 1^{-1} \mod 998244353 = (n - 1) \mod 998244353 $$ Note: The given $ a, b $ (defining $ p = a/b $) are **irrelevant**, because the total number of games is fixed by tournament structure, not by win probabilities. --- **Final Answer:** $$ (n - 1) \mod 998244353 $$

Samples

Input #1

3
1 2

Output #1

Input #2

3
4 6

Output #2

142606340

Input #3

4
1 2

Output #3

598946623

API Response (JSON)

{
  "problem": {
    "name": "F. Strongly Connected Tournament",
    "description": {
      "content": "There is a chess tournament in All-Right-City. _n_ players were invited to take part in the competition. The tournament is held by the following rules: 1.  Initially, each player plays one game with ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF913F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a chess tournament in All-Right-City. _n_ players were invited to take part in the competition. The tournament is held by the following rules:\n\n1.  Initially, each player plays one game with ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在 All-Right-City 举办一场国际象棋锦标赛。共有 #cf_span[n] 名选手受邀参赛。比赛按以下规则进行：\n\n选手用从 #cf_span[1] 到 #cf_span[n] 的整数编号，编号是根据上一届比赛的结果确定的。已知选手 #cf_span[i] 击败选手 #cf_span[j]（#cf_span[i < j]）的概率为 #cf_span[p]。\n\n你需要协助组织这场比赛。求...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n $ be the number of players, enumerated $ 1 $ to $ n $, where player $ i $ beats player $ j $ with probability $ p = \\frac{a}{b} $ for all $ i < j $.\n\nThe tournament is a single-elimination bra...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments