#1997. 路径计数

路径计数

路径计数

题目描述

标题: 路径计数 - Problem - QOJ.ac

#21436. 路径计数

Statistics

题目描述

给定一个包含 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