103145: [Atcoder]ABC314 F - A Certain Game

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

Description

Score : $475$ points

Problem Statement

$N$ players, player $1$, player $2$, ..., player $N$, participate in a game tournament. Just before the tournament starts, each player forms a one-person team, so there are $N$ teams in total.

The tournament has a total of $N-1$ matches. In each match, two different teams are chosen. One team goes first, and the other goes second. Each match will result in exactly one team winning. Specifically, for each $i = 1, 2, \ldots, N-1$, the $i$-th match proceeds as follows.

  • The team with player $p_i$ goes first, and the team with player $q_i$ goes second.
  • Let $a$ and $b$ be the numbers of players in the first and second teams, respectively. The first team wins with probability $\frac{a}{a+b}$, and the second team wins with probability $\frac{b}{a+b}$.
  • Then, the two teams are combined into a single team.

The result of each match is independent of those of the others.

For each of the $N$ players, print the expected number of times the team with that player wins throughout the tournament, modulo $998244353$.

How to print an expected value modulo $998244353$

It can be proved that the sought expected value is always rational. Also, the constraints of this problem guarantee that if the sought expected value is expressed as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998244353$.

Now, there is a unique integer $z$ between $0$ and $998244352$, inclusive, such that $xz \equiv y \pmod{998244353}$. Report this $z$.

Constraints

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq p_i, q_i \leq N$
  • Just before the $i$-th match, player $p_i$ and player $q_i$ belong to different teams.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$p_1$ $q_1$
$p_2$ $q_2$
$\vdots$
$p_{N-1}$ $q_{N-1}$

Output

For each $i = 1, 2, \ldots, N$, print $E_i$, the expected number, modulo $998244353$, of times the team with player $i$ wins throughout the tournament, separated by spaces, in the following format:

$E_1$ $E_2$ $\ldots$ $E_N$

Sample Input 1

5
1 2
4 3
5 3
1 4

Sample Output 1

698771048 698771048 964969543 964969543 133099248

We call a team formed by player $x_1$, player $x_2$, $\ldots$, player $x_k$ as team $\lbrace x_1, x_2, \ldots, x_k \rbrace$.

  • The first match is played by team $\lbrace 1 \rbrace$, with player $1$, and team $\lbrace 2 \rbrace$, with player $2$. Team $\lbrace 1 \rbrace$ wins with probability $\frac{1}{2}$, and team $\lbrace 2 \rbrace$ wins with probability $\frac{1}{2}$. Then, the two teams are combined into a single team $\lbrace 1, 2 \rbrace$.
  • The second match is played by team $\lbrace 4 \rbrace$, with player $4$, and team $\lbrace 3 \rbrace$, with player $3$. Team $\lbrace 4 \rbrace$ wins with probability $\frac{1}{2}$, and team $\lbrace 3 \rbrace$ wins with probability $\frac{1}{2}$. Then, the two teams are combined into a single team $\lbrace 3, 4 \rbrace$.
  • The third match is played by team $\lbrace 5 \rbrace$, with player $5$, and team $\lbrace 3, 4 \rbrace$, with player $3$. Team $\lbrace 5 \rbrace$ wins with probability $\frac{1}{3}$, and team $\lbrace 3, 4 \rbrace$ wins with probability $\frac{2}{3}$. Then, the two teams are combined into a single team $\lbrace 3, 4, 5 \rbrace$.
  • The fourth match is played by team $\lbrace 1, 2 \rbrace$, with player $1$, and team $\lbrace 3, 4, 5 \rbrace$, with player $4$. Team $\lbrace 1, 2 \rbrace$ wins with probability $\frac{2}{5}$, and team $\lbrace 3, 4, 5 \rbrace$ wins with probability $\frac{3}{5}$. Then, the two teams are combined into a single team $\lbrace 1, 2, 3, 4, 5 \rbrace$.

The expected numbers of times the teams with players $1, 2, 3, 4, 5$ win throughout the tournament, $E_1, E_2, E_3, E_4, E_5$, are $\frac{9}{10}, \frac{9}{10}, \frac{53}{30}, \frac{53}{30}, \frac{14}{15}$, respectively.


Sample Input 2

15
9 2
8 10
13 6
12 11
7 10
4 10
14 2
5 4
1 15
15 2
6 9
8 11
6 3
2 8

Sample Output 2

43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290

Output

分数:$475$分

问题描述

$N$个玩家,玩家$1$,玩家$2$,...,玩家$N$参加一个游戏比赛。在比赛开始前,每个玩家组成一个单人队伍,所以总共有$N$个队伍。

比赛总共有$N-1$场。每场比赛,选择两个不同的队伍。一个队伍先手,另一个队伍后手。每场比赛只会有一个队伍获胜。具体来说,对于每个$i = 1, 2, \ldots, N-1$,第$i$场比赛进行如下。

  • 玩家$p_i$所在的队伍先手,玩家$q_i$所在的队伍后手。
  • 设第一个队伍和第二个队伍的玩家数量分别为$a$和$b$。第一个队伍获胜的概率为$\frac{a}{a+b}$,第二个队伍获胜的概率为$\frac{b}{a+b}$。
  • 然后,这两个队伍合并为一个队伍。

每场比赛的结果与其他比赛的结果无关。

对于每个玩家,输出在整个比赛期间,该玩家所在的队伍获胜的期望次数,对$998244353$取模。

如何对$998244353$取模输出期望值

可以证明,所求的期望值总是有理数。此外,本问题的约束条件保证了,如果所求的期望值表示为不可约分数$\frac{y}{x}$,那么$x$不被$998244353$整除。

现在,存在一个唯一的整数$z$,其范围在$0$到$998244352$之间(包括这两个数),满足$xz \equiv y \pmod{998244353}$。报告这个$z$。

约束条件

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq p_i, q_i \leq N$
  • 在第$i$场比赛开始前,玩家$p_i$和玩家$q_i$属于不同的队伍。
  • 所有的输入值都是整数。

输入

输入从标准输入按以下格式给出:

$N$
$p_1$ $q_1$
$p_2$ $q_2$
$\vdots$
$p_{N-1}$ $q_{N-1}$

输出

对于每个$i = 1, 2, \ldots, N$,以空格分隔的方式输出$E_i$,即在整个比赛中,玩家$i$所在的队伍获胜的期望次数,对$998244353$取模,如下所示:

$E_1$ $E_2$ $\ldots$ $E_N$

样例输入 1

5
1 2
4 3
5 3
1 4

样例输出 1

698771048 698771048 964969543 964969543 133099248

我们称由玩家$x_1$,玩家$x_2$,$\ldots$,玩家$x_k$组成的队伍为队伍$\lbrace x_1, x_2, \ldots, x_k \rbrace$。

  • 第一场比赛由队伍$\lbrace 1 \rbrace$,包含玩家$1$,和队伍$\lbrace 2 \rbrace$,包含玩家$2$进行。队伍$\lbrace 1 \rbrace$获胜的概率为$\frac{1}{2}$,队伍$\lbrace 2 \rbrace$获胜的概率为$\frac{1}{2}$。然后,这两个队伍合并为一个队伍$\lbrace 1, 2 \rbrace$。
  • 第二场比赛由队伍$\lbrace 4 \rbrace$,包含玩家$4$,和队伍$\lbrace 3 \rbrace$,包含玩家$3$进行。队伍$\lbrace 4 \rbrace$获胜的概率为$\frac{1}{2}$,队伍$\lbrace 3 \rbrace$获胜的概率为$\frac{1}{2}$。然后,这两个队伍合并为一个队伍$\lbrace 3, 4 \rbrace$。
  • 第三场比赛由队伍$\lbrace 5 \rbrace$,包含玩家$5$,和队伍$\lbrace 3, 4 \rbrace$,包含玩家$3$进行。队伍$\lbrace 5 \rbrace$获胜的概率为$\frac{1}{3}$,队伍$\lbrace 3, 4 \rbrace$获胜的概率为$\frac{2}{3}$。然后,这两个队伍合并为一个队伍$\lbrace 3, 4, 5 \rbrace$。
  • 第四场比赛由队伍$\lbrace 1, 2 \rbrace$,包含玩家$1$,和队伍$\lbrace 3, 4, 5 \rbrace$,包含玩家$4$进行。队伍$\lbrace 1, 2 \rbrace$获胜的概率为$\frac{2}{5}$,队伍$\lbrace 3, 4, 5 \rbrace$获胜的概率为$\frac{3}{5}$。然后,这两个队伍合并为一个队伍$\lbrace 1, 2, 3, 4, 5 \rbrace$。

在整个比赛中,队伍$\lbrace 1, 2, 3, 4, 5 \rbrace$中玩家$1, 2, 3, 4, 5$获胜的期望次数分别为$\frac{9}{10}, \frac{9}{10}, \frac{53}{30}, \frac{53}{30}, \frac{14}{15}$。


样例输入 2

15
9 2
8 10
13 6
12 11
7 10
4 10
14 2
5 4
1 15
15 2
6 9
8 11
6 3
2 8

样例输出 2

43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290

HINT

n个人,有n-1场比赛,每次比赛两人(团体),根据团体人数决定胜负的概率,比赛后两人成为同一个团体,请问每个人期望赢多少次?

加入题单

上一题 下一题 算法标签: