UOJ Logo Universal Online Judge

UOJ

附件下载 统计

在你的帮助下,跳蚤国王发现把小队排列成理想情况是不可能的,于是他放弃了让小队重新排列的计划,直接下令强攻实验室。

在经过一番血战之后,跳蚤军队成功攻克了实验室中的大部分区域并把 picks 博士与他的猴子们逼入了最后一间房间中——同时也是存储了绝大部分资料和研究成果的最重要的房间。

这间房间的建造利用了跳蚤夸克神奇的力量,因此跳蚤国王发现强行闯入房间是不可能的,而唯一的入口——房间正门却被一个密码锁锁住了。

在这个密码锁上画了一张 n 个点的完全图,其中每一条边旁边都写了一个数字。跳蚤国王发现只有 m 条边对应的数字不是 5000(其他数字都是 5000

经过一番探索,跳蚤国王发现这个密码锁的密码等于这样一个问题的答案:

密码锁上给出了一张 n 个点的完全图,现在要给这个完全图的每一条边随机定向成一个有向图。对于一条边 (i,j)(i<j),这条边的方向是 ij 的概率是 numi,j10000numi,j 指这条边旁边的数字,否则就是 ji。在随机定向后,设这张有向图的强连通分量数目为 x,求 x×10000n(n1) 的期望,可以证明该期望值一定是一个整数。因为答案可能很大,所以只需要求出这个答案对 9982443537×17×223+1,一个质数 取模后的结果。

跳蚤国王发现这个问题并不是非常简单,于是他让你——这附近最著名的民间科学家来帮他计算这个问题的答案。

输入格式

第一行两个正整数 n,m,含义如题意所述。

接下来的m行中,第i行有三个整数ui,vi,wi,表示边(ui,vi)上的数字是wi。保证 ui<vi

输出格式

输出期望值对 998244353 取模后的值。

样例一

input

2 1
1 2 4096

output

200000000

explanation

图中只有一条边,有409610000的概率是从 12,有1409610000的概率是从 21。但是无论怎么定向该有向图连通分量数目都是 2,所以答案为2×100002×1=200000000

样例二

input

3 3
1 2 4000
2 3 6000
1 3 3000

output

296883784

explanation

图中有三条边,定向概率均已给出,容易发现有400010000×600010000×(1300010000)+(1400010000)×(1600010000)×300010000=0.24的概率图中只有一个强连通分量,10.24=0.76的概率图中有三个强连通分量,而100003×2=1024,所以答案为0.24×1×1024+0.76×3×1024=2,520,000,000,000,000,000,000,000,注意答案要模 998244353 后输出,因此答案为 296883784

样例三

input

6 15
1 2 10000
1 3 0
1 4 10000
1 5 10000
1 6 10000
2 3 10000
2 4 10000
2 5 10000
2 6 10000
3 4 10000
3 5 10000
3 6 10000
4 5 10000
4 6 0
5 6 10000

output

500494593

explanation

可以发现定向的图是固定的,只有{1,2,3}{4,5,6}两个强连通分量,因此答案为2×100006×5,注意对998244353取模。

样例四

input

4 0

output

99696143

explanation

注意没有输入的边的两个方向的定向概率均为0.5

样例五

input

5 4
1 5 10000
1 4 10000
1 3 10000
1 2 10000

output

985337417

explanation

容易看出期望强连通分量数是前一个图的期望强连通分量数加1,但是题目求的是强连通分量数乘以10000n(n1)的期望,因此答案相差甚远。

样例六

input

4 4
1 2 4194
1 3 9971
2 4 7191
1 4 1102

output

433654756

样例七

input

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

output

940436965

限制与约定

子任务分值限制与约定
119n6,m15
223n15,m15
37n38,m=0
424n30,m15
527n38,m19

对于所有数据, 1n38, 0m19, 0wi10000

对每一个i, 均有ui<vi

对于ij,保证uiujvivj,即没有重边,这意味着mn(n1)2

时间限制:1s

空间限制:256MB

下载

样例数据下载