UOJ Logo Universal Online Judge

UOJ

#181. 【UR #12】密码锁

附件下载 统计

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

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

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

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

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

密码锁上给出了一张 $n$ 个点的完全图,现在要给这个完全图的每一条边随机定向成一个有向图。对于一条边 $(i,j)(i < j)$,这条边的方向是 $i$ 到 $j$ 的概率是 $\frac{\mathrm{num}_{i,j}}{10000}$,$\mathrm{num}_{i,j}$ 指这条边旁边的数字,否则就是 $j$ 到 $i$。在随机定向后,设这张有向图的强连通分量数目为 $x$,求 $x \times 10000^{n(n-1)}$ 的期望,可以证明该期望值一定是一个整数。因为答案可能很大,所以只需要求出这个答案对 $998244353(7\times 17 \times 2^{23}+1$,一个质数$)$ 取模后的结果。

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

输入格式

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

接下来的$m$行中,第$i$行有三个整数$u_i, v_i, w_i$,表示边$(u_i, v_i)$上的数字是$w_i$。保证 $u_i < v_i$ 。

输出格式

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

样例一

input

2 1
1 2 4096

output

200000000

explanation

图中只有一条边,有$ \frac{4096}{10000} $的概率是从 $1$ 到 $2$,有$ 1 - \frac{4096}{10000} $的概率是从 $2$ 到 $1$。但是无论怎么定向该有向图连通分量数目都是 $2$,所以答案为$ 2 \times 10000 ^ {2 \times 1} = 200000000 $。

样例二

input

3 3
1 2 4000
2 3 6000
1 3 3000

output

296883784

explanation

图中有三条边,定向概率均已给出,容易发现有$ \frac{4000}{10000} \times \frac{6000}{10000} \times (1 - \frac{3000}{10000}) + (1 - \frac{4000}{10000}) \times (1 - \frac{6000}{10000}) \times \frac{3000}{10000} = 0.24$的概率图中只有一个强连通分量,$1 - 0.24 = 0.76$的概率图中有三个强连通分量,而$ 10000 ^ {3 \times 2} = 10 ^ {24} $,所以答案为$ 0.24 \times 1 \times 10 ^ {24} + 0.76 \times 3 \times 10 ^ {24} = 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 \times 10000 ^ {6 \times 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,但是题目求的是强连通分量数乘以$10000 ^ { n(n - 1) }$的期望,因此答案相差甚远。

样例六

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

限制与约定

子任务分值限制与约定
119$n \le 6, m \le 15$
223$n \le 15, m \le 15$
37$n \le 38, m = 0$
424$n \le 30, m \le 15$
527$n \le 38, m \le 19$

对于所有数据, $1 \le n \le 38$, $0 \le m \le 19$, $0 \le w_i \le 10000$。

对每一个$i$, 均有$u_i < v_i$。

对于$i \neq j$,保证$u_i \neq u_j$或$v_i \neq v_j$,即没有重边,这意味着$m \le \frac{n(n - 1)}{2}$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载