#P18773. [2027年国家集训队互测] Path Counting

[2027年国家集训队互测] Path Counting

Path Counting

题目描述

给定一个包含 nn 个点、mm 条带权边的有向图,点编号为 1,2,…,n1,2,\ldots,n。没有自环,任意有序点对间至多一条边。边 u→vu\to v 权值为 wu,vw_{u,v}。另给定数组 f0,f1,…,f2n−1f_0,f_1,\ldots,f_{2^n-1}。对于点集 SS,其权为 fmask⁡(S)f_{\operatorname{mask}(S)},其中 mask⁡(S)=∑v∈S2v−1\operatorname{mask}(S)=\sum_{v\in S}2^{v-1}。

对每个有序点对 (s,t)(s,t),满足下列条件的序列 p0,p1,…,pℓp_0,p_1,\ldots,p_\ell 称为从 ss 到 tt 的简单路径:

  • ℓ≥0\ell\ge0,p0=s,pℓ=tp_0=s,p_\ell=t;
  • 对所有 0≤i<ℓ0\le i<\ell,存在边 pi→pi+1p_i\to p_{i+1};
  • 中间点 p1,…,pℓ−1p_1,\ldots,p_{\ell-1} 两两不同,且均不等于 s,ts,t。

设路径经过的点集为 SS,贡献为

$$f_{\operatorname{mask}(S)}\prod_{i=0}^{\ell-1}w_{p_i,p_{i+1}}.$$

求每个有序点对所有简单路径的贡献之和,模 998244353998244353。特别地,s=ts=t 时既允许零长度单点路径,也允许中间点不重复的简单有向回路;零长度的空乘积为1。

输入格式

第一行 n,mn,m。接下来 mm 行,每行 u,v,wu,v,w,表示一条从 uu 到 vv、权为 ww 的边。接下来一行 2n2^n 个整数,依次为 f0,…,f2n−1f_0,\ldots,f_{2^n-1}。

输出格式

输出 nn 行,每行 nn 个整数,第 ss 行第 tt 个为 (s,t)(s,t) 的答案,模 998244353998244353。

样例

输入:

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→31\to3,贡献 f5×5=25f_5\times5=25;1→2→31\to2\to3,贡献 f7×2×3=42f_7\times2\times3=42,共67。 从1到1有单点1,贡献 f1=1f_1=1;1→3→11\to3\to1,贡献 f5×5×7=175f_5\times5\times7=175;1→2→3→11\to2\to3\to1,贡献 f7×2×3×7=294f_7\times2\times3\times7=294,共470。其它点对同理。

数据范围

1≤n≤211\le n\le21,0≤m≤n(n−1)0\le m\le n(n-1),1≤u,v≤n1\le u,v\le n,u≠vu\ne v,有序点对无重边;0≤w,fi<9982443530\le w,f_i<998244353。权为0的边合法。f0f_0 也给出,但路径点集非空。

子任务如下:

子任务 分值 特殊限制 依赖
1 20 n≤16n\le16 无
2 15 f2n−1=1f_{2^n-1}=1,其余fi=0f_i=0
3 对$ S
4 20 所有fi=1f_i=1 无
5 30 无 1、2、3、4