QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[0]

# 8947. 白兔迷宫

Statistics

题目描述

白兔进入了一个迷宫。迷宫是一个 n 个点 m 条边的有向图,图上可能有重边和自环。节点从 1n 编号,起点为 S,终点为 T。保证从任意一个点出发都存在一条路径到达 T

迷宫的每条边上有一个怪物,怪物有 01 两类。白兔有一个积分,初始为 0。每当白兔经过一条边,

  • 若这条边上是一个 1 类怪物,白兔会将它击杀获得 1 的积分,并走到这条边的终点;
  • 若这条边上是一个 0 类怪物,白兔会被其打晕。怪物不会把白兔打死,但是会清空白兔之前获得的所有积分,然后把白兔放在这条边的终点。

经过一条边后这条边上的怪物会刷新,所以白兔多次经过一条边会多次触发怪物的效果。

由于白兔不知道迷宫的结构,所以白兔决定随机游走,即从 S 出发,每次从当前点独立等概率随机一条出边移动,触发对应边上怪物的效果并到达这条边的终点。当白兔第一次走到 T 时,游走就结束了。

给出这张图的结构以及每条边上怪物的类型,定义 X 表示游走完成时的积分对应的随机变量,白兔想让你帮他回答两个问题:

  1. X 的期望是多少;
  2. X 的方差是多少。

由于白兔不喜欢实数,你只需要输出其对 998244353 取模的结果。在题设条件下,容易发现答案一定是有理数,且将答案化为既约分数形式后分母不为 998244353 的倍数。

输入格式

从标准输入读入数据。

输入的第一行包含四个整数 n,m,S,T,表示迷宫的点数、边数、起点、终点。

接下来 m 行,每行三个整数 x,y,o,表示一条 xy 的有向边以及这条边上的怪物类型。

输出格式

输出到标准输出。

输出一行两个整数,第一个整数表示积分的期望,第二个整数表示积分的方差。

样例

输入

2 2 1 2
1 1 1
1 2 1

输出

2 2

解释

1 号点出发有一个自环和一条通往 2 号点的边。每条边都有 o=1,因此积分就等于随机游走的步数。

对于 x>0,最终积分为 x 当且仅当白兔先在 1 号点走 x1 次自环,第 x 次走到 2 号点,因此积分为 x 的概率为 2x。故期望为 x=1x2x=2,方差为 +x=1(x2)22x=2.

子任务

对于所有测试数据,

  • 2n1001mn2
  • 1S,TnST
  • 1x,yn0o1
  • 从任意一个点出发都存在一条路径到达 T

Subtask 1(4pts):o=0

Subtask 2(24pts):o=1

Subtask 3(8pts):m=n1,图上仅有 S 入度为 0,仅有 T 出度为 0

Subtask 4(20pts):给出的图没有环

Subtask 5(44pts):没有特殊限制

评分方式

对于每个测试点,你每正确回答一个问题,可以获得该测试点 50% 的分数。每个子任务的得分为其中所有测试点得分的最小值。

提示

对一个值域为自然数集的随机变量 X,若 X=x 的概率为 Px,那么 X 的期望定义为 E[X]=+x=0xPx, X 的方差定义为 Var[X]=E[(XE[X])2]=+x=0(xE[X])2Px.