UOJ Logo Universal Online Judge

UOJ

#372. 【UR #17】滑稽树前做游戏

统计

小时候的你听说,如果在滑稽树丰收的时候,手牵着手吃下滑稽果,那么就可以心意相通,永世不离。于是兴奋的你带上了小书包,在滑稽树下等着熟透的滑稽果落下。

这天,你一共捡到了 $n$ 颗滑稽果,其中第 $i$ 颗滑稽果的价值是 $w_i$。然而你的小书包实在是太小了,只能装下一颗滑稽果或者两颗形状比较契合的滑稽果。

经过一番尝试,你发现了只有 $m$ 对滑稽果 $(a_i,b_i)$ 可以被同时放进书包中。于是你轻易地找到了价值和最大的组合,并和青梅竹马的她度过了一个浪漫的夜晚。

虽然时光渐渐地逝去,但是童年时的浪漫一直埋藏在你们的心里。现在,你和你的她打算在明天——一年一度滑稽树收获的日子,在滑稽树下回忆儿时的美好。

在出发之前,你想起了你的小书包以及那些滑稽果。虽然你仍然记得哪 $m$ 对滑稽果是契合的,但是每一个滑稽果的价格却是无论如何也回忆不起来了。于是你打算简单的估计一下当时带回去的滑稽果的价值和:你假设每个滑稽果的价值都是 $[0,1]$ 之间的均匀随机变量,且都是独立的,你想要计算带回去的滑稽果价值的期望。

下面形式化地给出题意:$x_1,x_2,...,x_n$ 为 $n$ 个独立随机变量,且均服从 $[0,1]$ 上的均匀分布。给出 $m$ 对关系 $(a_i,b_i)$,令 $f(x) = \max(\max_{i=1}^nx_i,\max_{i=1}^m(x_{a_i}+x_{b_i}))$,求 $f(x)$ 的期望。

输入格式

第一行两个正整数 $n,m$,表示滑稽果的数量与形状契合的对数。

接下来 $m$ 行每行两个整数 $a_i,b_i(1 \leq a_i < b_i \leq n)$,表示一对契合的滑稽果。

输出格式

一行一个整数表示答案,模 $998244353$($7 \times 17 \times 2^{23} + 1$,一个质数)后输出。即如果答案可以表示为最简分数 $\frac{x}{y}$ 的形式,你需要输出 $x \times y^{-1} \mod 998244353$。

样例一

input

3 2
1 2
2 3

output

166374060

explanation

不难发现答案一定是 $\max(x_1,x_3)+x_2$,其中 $\max(x_1,x_3)$ 的期望是 $\frac{2}{3}$,$x_2$ 的期望是 $\frac{1}{2}$,所以 $f(x)$ 的期望是 $\frac{7}{6}$,在模 $998244353$ 意义下是 $166374060$。

样例二

input

5 0

output

831870295

explanation

答案是 $\max_{i=1}^n x_i$,即 $\frac{5}{6}$,在模 $998244353$ 意义下是 $831870295$。

样例三

input

5 7
1 2
2 3
3 4
4 5
1 3
3 5
2 4

output

776412276

样例四

见样例数据下载,$n = 10$,满足性质二(见限制与约定)。

样例五

见样例数据下载,$n = 10$。

限制与约定

由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 $5$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

子任务 分值 $n$ 的规模 其他
1$10$$n \leq 25$满足性质一
2$20$满足性质二
3$20$$n \leq 4$
4$20$$n \leq 10$
5$20$$n \leq 15$
6$10$$n \leq 25$

性质一:$m = n -1$,且 $a_i = 1$。

性质二:如果将滑稽果看做点,契合关系看做边,那么得到的图是一棵树。

对于 $100\%$ 的数据,$n \geq 1, 0 \leq m \leq \frac{n(n-1)}{2}$,保证不会有任何两对契合关系相同。

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

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

下载

样例数据下载