一棵树

Desciption

给定一棵 $n$ 个点的树。你需要删除 $k$ 条边，然后添加 $k$ 条边，使得新图仍然是一棵树。定义两种方案不同当且仅当删除的边集合不同或添加的边集合不同。

定义一棵树的价值为任意两点间的距离的和。求所有方案的价值和模 $998244353$。

Hints

对于 $22\%$ 的数据, 满足 $n \leq 100$

对于另外 $9 \%$ 的数据, 满足 $k = 0$

对于另外 $17 \%$ 的数据,满足树的形态是一条链

对于全部数据, $0 \leq k \leq 1, 1 \leq n \leq 10^5$

代金券

Desciption

有 $n$ 个菜品,每个菜品价格为 $v_i$ 元. 马老师要依次品尝这 $n$ 个菜品. 若每次购买的菜品价格为 $a$, 他可以使用 $b (0 \leq b \leq a)$ 张代金券,每张代金券相当于 $1$ 元.也就是他用 $b$ 张代金券后仍需支付 $a - b$ 元.同时,他可以获得 $\lfloor \frac{a-b}{c} \rfloor$ 张代金券,其中 $c$ 是给定的正整数.

马老师最开始一张代金券也没有. 食堂的菜品价格有 $q$ 次变动. 对于每次变动,食堂会更改一个菜品的价格.每一次变动后马老师都想知道他最少要花多少钱,才能依次品尝 $n$ 个菜品.

Hints

对于 $11\%$ 的数据,满足 $n \leq 100, q \leq 50, c \leq 100, a_i \leq 100$

对于所有数据, $1 \leq n, q \leq 10^5, 1 \leq c \leq 10^9, 1 \leq a_i \leq 10^{12}$

招新

Description

在 $[0,m]$ 中随机选 $n$ 个实数点，请问不存在 $3$ 个点在同一长度为 $k$ 的区间中的概率为多少，对 $p$ 取模。

Hints

$1 \leq n \leq 50, 1 \leq m, k \leq 150, 10^8 \leq p \leq 10^9$, 保证 $p$ 是质数.