传送门（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
5
1 2 1 4
4 2 2 5 4
5 1 5 5 5
4
4 3 5
2 1 5
1 2 4
2 5 4
样例输出 #1
142606350
199648884
15
14
623902734
提示
对于所有测试点，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 次方求和。
形式化地，请你计算
输入格式
第一行输入两个正整数 n,k。
第二行输入 n 个正整数，即输入排列 p。
输出格式
输出答案，由于答案可能比较大，请输出它模 998244353 后的结果。
样例 #1
样例输入 #1
10 1
2 1 10 3 5 9 4 7 6 8
样例输出 #1
4948
样例 #2
样例输入 #2
10 2
2 1 10 3 5 9 4 7 6 8
样例输出 #2
16614
样例 #3
样例输入 #3
10 3
2 1 10 3 5 9 4 7 6 8
样例输出 #3
74224
提示
对于 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
475385730
984256801
786260176
748830353
样例 #3
样例输入 #3
12
42 88 13 11 71 55 32 13 72 53 37 50
样例输出 #3
576548830
535668176
655795435
571472426
687573612
201265174
837771620
858086700
272761418
825332069
479805598
485629414
样例 #4
样例输入 #4
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样例输出 #4
944216943
754663931
182871577
227593884
881798715
63696191
849286979
10164579
465663858
112142932
112142932
465663858
10164579
849286979
63696191
881798715
227593884
182871577
754663931
944216943
提示
【样例解释】
第一组样例中，三位选手获胜的概率分别为 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分）：无特殊限制
