#1824. 白兔迷宫

    ID: 1824 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1786来源:qoj.ac数据:公开样例数学

白兔迷宫

白兔迷宫

题目描述

标题: 白兔迷宫 - Problem - QOJ.ac

#8947. 白兔迷宫

Statistics

The problem was used in the following contests:

题目描述

白兔进入了一个迷宫。迷宫是一个 n 个点 m 条边的有向图,图上可能有重边和自环。节点从 1 到 n 编号,起点为 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,表示一条 x 到 y 的有向边以及这条边上的怪物类型。

输出格式

输出到标准输出。

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

样例

输入

2 2 1 2
1 1 1
1 2 1

输出

2 2

解释

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

对于 x>0,最终积分为 x 当且仅当白兔先在 1 号点走 x−1 次自环,第 x 次走到 2 号点,因此积分为 x 的概率为 2−x。故期望为

∑x=1∞x2−x=2,

方差为

∑x=1+∞(x−2)22−x=2.

子任务

对于所有测试数据,

  • 2≤n≤100,1≤m≤n2;
  • 1≤S,T≤n,S≠T;
  • 1≤x,y≤n,0≤o≤1。
  • 从任意一个点出发都存在一条路径到达 T。

Subtask 1(4pts):o=0

Subtask 2(24pts):o=1

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

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

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

评分方式

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

提示

对一个值域为自然数集的随机变量 X,若 X=x 的概率为 Px,那么 X 的期望定义为

E[X]=∑x=0+∞xPx,

X 的方差定义为

Var[X]=E[(X−E[X])2]=∑x=0+∞(x−E[X])2Px.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 2 1 2
1 1 1
1 2 1
2 2