传送门（portal）[弱化版]

题目描述

你在一条长为 $n$ 的链上，但是你只能通过一些传送门来到达其他位置，使用一个传送门需要时间，你的任务是计算出对于每一个单独的位置，到达那里需要的最短时间，或者无法到达。

一个传送门由两侧组成，一侧从 $u$ 到 $v$ ，另一侧从 $x$ 到 $y$ 。传送门是双向的，这意味着你只要站在 $u$ 到 $v$ 的路径中的任何一个位置，就可以通过传送门到达 $x$ 到 $y$ 的路径的任何一个位置，反之亦然。你也可以使用一个传送门多次，这意味着你如果在 $u$ 到 $v$ 的路径中，你可以传送 2 次到达 $u$ 到 $v$ 路径上的任何一个位置。

输入格式

第一行三个正整数 $n, m, s$ 表示节点数、传送门数和你所在的位置。

接下来 $m$ 行，每行 5 个整数 $u\ v\ x\ y\ t$ 满足 $1 \le u, v, x, y \le n$ ，表示一组传送门的两端以及消耗时间。

输出格式

输出一行， $n$ 个整数，第 $i$ 个表示 $s$ 到 $i$ 所需要的时间，如果无法到达则输出 $-1$ 。

样例 #1

样例输入 #1

6 2 1
1 1 2 3 0
3 3 5 6 0

样例输出 #1

0 0 0 -1 0 0

提示

对于 $100\%$ 的数据，保证 $n, m \le 10^3, 0 \le t \le 10^5$

测试点	$n\le$	$m\le$	$t=0$
$1,2,3$	$200$	$200$	√
$4,5,6$	$200$	$200$
$7,8$	$10^3$	$10^3$	√
$9,10$	$10^3$	$10^3$

随机爬树（climb）

题目描述

给定 $n$ 个点有根树， $1$ 为根。每个点有权值 $w_u$ （ $w_u$ 一定为正）和 $a_u$ 。从根节点出发，以一种随机的方式走到某一个叶节点。随机方式如下。

当前点为 $u$ ， $u$ 不是叶节点。记 $u$ 的所有儿子的 $w$ 的和为 $sum_u$ ，则 $u$ 走到某一个儿子 $v$ 的概率为 $\frac{w_v}{sum_u}$ 。

一次行走的得分为沿途所有节点的 $a$ 之和。

有 $q$ 次修改。每次会单点修改某个点的 $w$ 和 $a$ 。

希望求出初始状态和每次修改后，得分的期望。答案对 $998244353$ 取模。保证在任意时刻，所有非叶节点 $u$ 的 $sum_u$ 都不为 $998244353$ 的倍数。

输入格式

第一行 $1$ 个正整数n代表节点个数。

第二行 $n-1$ 个正整数表示 $2-n$ 号节点的父节点，每个节点的父节点编号小于自己的。

第三行 $n$ 个正整数表示每个节点的 $w$ 。

第四行 $n$ 个正整数表示每个节点的 $a$ 。

第五行 $1$ 个整数 $q$ 表示修改次数。

接下来 $q$ 行每行三个正整数 $u, w, a$ ，表示将 $u$ 号节点的 $w, a$ 权值赋值为输入的 $w, a$ 。

输出格式

$q+1$ 行，每行一个整数，表示在树的每一个状态下，得分的期望对 $998244353$ 取模。

样例 #1

样例输入 #1

样例输出 #1

提示

对于所有测试点， $1 \leq w, a \leq 100000$ ，并且保证每一时刻的每一非叶节点 $u$ 的 $sum_u$ 不被 $998244353$ 整除

对于60%的数据， $1 \leq n, q \leq 1000$

对于100%的数据， $1 \leq n, q \leq 100000$

【样例1解释】

5个答案对应的分数分别为： $\frac{97}{7},$ $\frac{67}{5},$ $15,$ $14,$ $\frac{107}{8}$

EINOIP2021 D1T3 数点（points）

题目描述

给一个排列 $p$ ，对每个 $i$ ，我们在平面上放置点 $(i,p_i)$ 。对于坐标上下限都在 $1\sim n$ 内的全体 $\left(\frac {n(n+1)}{2}\right)^2$ 种矩形，请你对每个矩形内部点数的 $k$ 次方求和。

形式化地，请你计算

\sum_{1\le l\le r\le n} \sum_{1\le d\le u\le n} \left|\left\{ i\mid l\le i\le r \land d\le p_i\le u \right\}\right|^k

输入格式

第一行输入两个正整数 $n,k$ 。

第二行输入 $n$ 个正整数，即输入排列 $p$ 。

输出格式

输出答案，由于答案可能比较大，请输出它模 $998244353$ 后的结果。

样例 #1

样例输入 #1

10 1
2 1 10 3 5 9 4 7 6 8

样例输出 #1

样例 #2

样例输入 #2

10 2
2 1 10 3 5 9 4 7 6 8

样例输出 #2

样例 #3

样例输入 #3

10 3
2 1 10 3 5 9 4 7 6 8

样例输出 #3

提示

对于 $100\%$ 的数据，保证 $1\le n\le 10^5; 1\le k\le 3$ 。

数据点编号	$n=$	$k=$
$1$	$50$	$3$
$2$	$300$	$1$
$3$	$300$	$2$
$4$	$300$	$3$
$5$	$3000$	$1$
$6$	$3000$	$2$
$7$	$3000$	$3$
$8$	$10^5$	$1$
$9$	$10^5$	$2$
$10$	$10^5$	$3$

比赛

题目描述

小 L 要参加一场比赛。

参加比赛的共有 $n$ 名选手。名选手排成一行，从左到右第 $i$ 位选手的实力用正整数 $a[i]$ 表示。如果两名实力分别为 $x,y$ 的选手单挑，则获胜的概率分别为 $x/(x+y), y/(x+y)$ 。

比赛由 $n-1$ 轮组成，在每一轮中，一对相邻选手会被选出进行单挑。每对相邻选手被选择的概率是相等的。在这场单挑中输掉的一方会离开比赛，其余的选手进入下一轮，相对位置保持不变。 $n-1$ 轮过后，剩下的一名选手即为比赛的胜者。

小 L 认为，这样的比赛并不公平，因为即使所有选手实力相同，不同位置上的选手获胜的可能性也是不一样的。因此，小 L 想让你求出每名选手获胜的概率（mod 998244353）。

输入格式

第一行一个整数 $n$ ，表示参加比赛的人数。

第二行 $n$ 个整数 $a[i]$ ，表示每位选手的实力。

输出格式

输出 $n$ 行，代表每位选手获胜的概率。

样例 #1

样例输入 #1

3
1 2 3

样例输出 #1

881782512
465847365
648858830

样例 #2

样例输入 #2

4
2103 2019 1911 2331

样例输出 #2

样例 #3

样例输入 #3

12
42 88 13 11 71 55 32 13 72 53 37 50

样例输出 #3

样例 #4

样例输入 #4

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

样例输出 #4

提示

【样例解释】

第一组样例中，三位选手获胜的概率分别为 $11/60, 4/15, 11/20$ 。第一位选手要获胜，有三种情况：

第一位选手先后击败第二位和第三位选手。这种情况发生的概率为 $1/2 \times 1/(1+2) \times 1/(1+3) = 1/24$ 。
第二位选手先击败第三位选手，然后被第一位选手击败。这种情况发生的概率为 $1/2 \times 2/(2+3)\times 1/(1+2) = 1/15$
第三位选手先击败第二位选手，然后被第一位选手击败。这种情况发生的概率为 $1/2\times 3/(2+3) \times 1/(1+3) = 3/40$

因此，第一位选手获胜的概率为 $1/24 + 1/15 + 3/40 = 11/60$

【数据范围】

对于所有测试点 $1\le n \le 500, 1\le a[i] \le 499122176$ ，保证答案不是 998244353 的倍数。

子任务1（3分）： $n\le 8$

子任务2（5分）： $n\le 10$

子任务3（17分）： $n\le 20$

子任务4（20分）： $n\le 60$

子任务5（20分）： $n\le 150$

子任务6（15分）： $a[i]=1$

子任务7（20分）：无特殊限制