#1997. 路径计数
路径计数
路径计数
题目描述
标题: 路径计数 - Problem - QOJ.ac
#21436. 路径计数
题目描述
给定一个包含 n 个点、m 条带权边的有向图,点的编号为 1,2,…,n。图中没有自环,且任意有序点对之间至多存在一条边。记边 u→v 的权值为 wu,v。
另给定数组 f0,f1,…,f2n−1。对于点集 S,定义其权值为 fmask(S),其中 mask(S)=∑v∈S2v−1。
对于每个有序点对 (s,t),称满足以下条件的点序列 p0,p1,…,pℓ 为从 s 到 t 的简单路径:
- ℓ≥0,p0=s, pℓ=t。
- ∀0≤i<ℓ,图中存在边 pi→pi+1。
- 中间点 p1,p2,…,pℓ−1 两两不同,且均不等于 s,t。
设一条简单路径经过的点构成的点集为 S,定义其贡献为点集 S 的权值与沿途所有边权的乘积,即
fmask(S)⋅∏i=0ℓ−1wpi,pi+1.
请对每个有序点对 (s,t),求从 s 到 t 的所有简单路径的贡献之和,并对 998244353 取模。
输入格式
第一行包含两个整数 n,m,表示图的点数和边数。
接下来 m 行,每行包含三个整数 u,v,w,表示存在一条从 u 指向 v,权值为 w 的有向边。
接下来一行包含 2n 个整数,依次为 f0,f1,…,f2n−1。
输出格式
输出 n 行,每行包含 n 个整数。
第 s 行第 t 个整数表示有序点对 (s,t) 的答案,对 998244353 取模。
样例
样例输入 #1
3 4
1 2 2
2 3 3
1 3 5
3 1 7
0 1 2 4 3 5 6 7
样例输出 #1
470 8 67
147 296 18
35 98 472
样例解释 #1
从 1 到 3 有两条简单路径:
- 路径 1→3 经过的点集为 {1,3},贡献为 f5×5=25。
- 路径 1→2→3 经过的点集为 {1,2,3},贡献为 f7×2×3=42。
因此,点对 (1,3) 的答案为 25+42=67。
从 1 到 1 有三条简单路径:
- 单点路径 1,贡献为 f1=1。
- 路径 1→3→1 经过的点集为 {1,3},贡献为 f5×5×7=175。
- 路径 1→2→3→1 经过的点集为 {1,2,3},贡献为 f7×2×3×7=294。
因此,点对 (1,1) 的答案为 1+175+294=470。
其他点对的答案也可同理得出。
数据范围
对于所有测试数据,保证:
- 1≤n≤21;
- 0≤m≤n(n−1);
- 1≤u,v≤n,且 u≠v;
- 任意有序点对之间至多存在一条边;
- 0≤w,fi<998244353。
本题采用子任务捆绑测试。各子任务的分值、特殊限制及依赖关系如下:
子任务 分值 特殊限制 依赖子任务 1 20 n≤16 无 2 15 f2n−1=1,其余 fi 均为 0 无 3 15 对所有满足 |S|≤n−2 的点集 S,均有 fmask(S)=0 2 4 20 所有 fi 均为 1 无 5 30 无特殊限制 1、2、3、4
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 4
1 2 2
2 3 3
1 3 5
3 1 7
0 1 2 4 3 5 6 7
470 8 67
147 296 18
35 98 472