304791: CF913F. Strongly Connected Tournament

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Strongly Connected Tournament

题意翻译

这是一个在All-Right城的国际象棋比赛。n个运动员被邀请参加比赛,比赛依照以下规则举办: 1. 期初,每个运动员与其他每一个运动员比赛,他们之间没有任何关系。 2. 在比赛之后,组织者造了一副有向的完全图,这张图把每名运动员看做点,对于每对运动员他们之间有一条边:他们之间比赛的胜利者是这条边的起点,输了的人是终点。 3. 然后对原图进行缩点,之后这张图变成了由原图的强连通分量组成的一条链A1→ A2→A3→……→Ak 4. 之后对将强联通分量A1里的点放到|A1|里面,将强联通分量A2中的所有点放入|A2|里面,以此类推 5. 为了确定每个运动员在各自强联通分量中的排名,需要再在每个强联通分量中将不断地进行1-5这五个步骤,也就是说,Ai中的k个人都需要和其他的k-1个人再比赛一次。 6. 如果一个强联通分量里只有一个人,那么他已经没有对手了,那么他的水平就已经确定了,就可以不用继续进行了。 运动员们被标号为1到n,标号被用在最初的图上。我们知道运动员i能赢运动员j的概率为p(i<j)。 你需要去帮助组织比赛,求出比赛总场数的期望值。 答案显然可以表示成P/Q,答P,Q为互质的整数。且Q不等于0。 输出P乘上Q相对于998244353的逆元。 简而言之答案对998244353取模。 输入输出格式 输入格式 第一行是一个单独的整数n ,2<=n<=2000 ,表示运动员的个数 第二行包括两个整数a和b ,1<=a,b<=100 ,p=a/b 输出格式: 输出总比赛场数的期望值,对998244353取模 如果对这个定义很陌生点英文题面中蓝色的here 感谢 @doge233 提供的翻译。

题目描述

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF913F/73744c721d90a72af450f8d7dbedc94cb5d41d4f.png) places, the players from the component $ A_{2} $ are placed on the next ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF913F/b09871082e46761fa1e7e95a7aded943a6e2f99d.png) 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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF913F/2c40be71c60fe708ee9e4e80e2cd7a26163f3bd6.png), where $ P $ and $ Q $ are coprime integers and ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF913F/660186d645b69bba4bba5848de2ac09458cd0b37.png). 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).

输入输出格式

输入格式


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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF913F/15a8e63bf5f367458cda7a05a3a86bf47f6d51e3.png).

输出格式


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.

输入输出样例

输入样例 #1

3
1 2

输出样例 #1

4

输入样例 #2

3
4 6

输出样例 #2

142606340

输入样例 #3

4
1 2

输出样例 #3

598946623

说明

In the first example the expected value is $ 4 $ . In the second example the expected value is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF913F/f4f87534b7ca561bf38de98427bc65be73b7b872.png). In the third example the expected value is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF913F/567be6e236ad10aea1dc58c16e74bafb83048d46.png).

Input

题意翻译

这是一个在All-Right城的国际象棋比赛。n个运动员被邀请参加比赛,比赛依照以下规则举办: 1. 期初,每个运动员与其他每一个运动员比赛,他们之间没有任何关系。 2. 在比赛之后,组织者造了一副有向的完全图,这张图把每名运动员看做点,对于每对运动员他们之间有一条边:他们之间比赛的胜利者是这条边的起点,输了的人是终点。 3. 然后对原图进行缩点,之后这张图变成了由原图的强连通分量组成的一条链A1→ A2→A3→……→Ak 4. 之后对将强联通分量A1里的点放到|A1|里面,将强联通分量A2中的所有点放入|A2|里面,以此类推 5. 为了确定每个运动员在各自强联通分量中的排名,需要再在每个强联通分量中将不断地进行1-5这五个步骤,也就是说,Ai中的k个人都需要和其他的k-1个人再比赛一次。 6. 如果一个强联通分量里只有一个人,那么他已经没有对手了,那么他的水平就已经确定了,就可以不用继续进行了。 运动员们被标号为1到n,标号被用在最初的图上。我们知道运动员i能赢运动员j的概率为p(i<j)。 你需要去帮助组织比赛,求出比赛总场数的期望值。 答案显然可以表示成P/Q,答P,Q为互质的整数。且Q不等于0。 输出P乘上Q相对于998244353的逆元。 简而言之答案对998244353取模。 输入输出格式 输入格式 第一行是一个单独的整数n ,2<=n<=2000 ,表示运动员的个数 第二行包括两个整数a和b ,1<=a,b<=100 ,p=a/b 输出格式: 输出总比赛场数的期望值,对998244353取模 如果对这个定义很陌生点英文题面中蓝色的here 感谢 @doge233 提供的翻译。

加入题单

上一题 下一题 算法标签: