题目描述
白兔进入了一个迷宫。迷宫是一个 n 个点 m 条边的有向图,图上可能有重边和自环。节点从 1 到 n 编号,起点为 S,终点为 T。保证从任意一个点出发都存在一条路径到达 T。
迷宫的每条边上有一个怪物,怪物有 01 两类。白兔有一个积分,初始为 0。每当白兔经过一条边,
- 若这条边上是一个 1 类怪物,白兔会将它击杀获得 1 的积分,并走到这条边的终点;
- 若这条边上是一个 0 类怪物,白兔会被其打晕。怪物不会把白兔打死,但是会清空白兔之前获得的所有积分,然后把白兔放在这条边的终点。
经过一条边后这条边上的怪物会刷新,所以白兔多次经过一条边会多次触发怪物的效果。
由于白兔不知道迷宫的结构,所以白兔决定随机游走,即从 S 出发,每次从当前点独立等概率随机一条出边移动,触发对应边上怪物的效果并到达这条边的终点。当白兔第一次走到 T 时,游走就结束了。
给出这张图的结构以及每条边上怪物的类型,定义 X 表示游走完成时的积分对应的随机变量,白兔想让你帮他回答两个问题:
- X 的期望是多少;
- 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=1x2−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=0xPx, X 的方差定义为 Var[X]=E[(X−E[X])2]=+∞∑x=0(x−E[X])2Px.