Path Counting
题目描述
给定一个包含 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,…,pℓ−1 两两不同,且均不等于 s,t。
设路径经过的点集为 S,贡献为
$$f_{\operatorname{mask}(S)}\prod_{i=0}^{\ell-1}w_{p_i,p_{i+1}}.$$
求每个有序点对所有简单路径的贡献之和,模 998244353。特别地,s=t 时既允许零长度单点路径,也允许中间点不重复的简单有向回路;零长度的空乘积为1。
输入格式
第一行 n,m。接下来 m 行,每行 u,v,w,表示一条从 u 到 v、权为 w 的边。接下来一行 2n 个整数,依次为 f0,…,f2n−1。
输出格式
输出 n 行,每行 n 个整数,第 s 行第 t 个为 (s,t) 的答案,模 998244353。
样例
输入:
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
从1到3有两条简单路径:1→3,贡献 f5×5=25;1→2→3,贡献 f7×2×3=42,共67。
从1到1有单点1,贡献 f1=1;1→3→1,贡献 f5×5×7=175;1→2→3→1,贡献 f7×2×3×7=294,共470。其它点对同理。
数据范围
1≤n≤21,0≤m≤n(n−1),1≤u,v≤n,u=v,有序点对无重边;0≤w,fi<998244353。权为0的边合法。f0 也给出,但路径点集非空。
子任务如下:
| 子任务 |
分值 |
特殊限制 |
依赖 |
| 1 |
20 |
n≤16 |
无 |
| 2 |
15 |
f2n−1=1,其余fi=0 |
| 3 |
对$ |
S |
| 4 |
20 |
所有fi=1 |
无 |
| 5 |
30 |
无 |
1、2、3、4 |