送你一个 DAG

Description
送你一个 n 个点 m 条边的 DAG 和参数 k, 定义一条经过 l 条边的路径的权值为 l
k
.
对于 i = 1…n, 求出所有 1 到 i 的路径的权值之和, 对 998244353 取模.
1.2 Input Format
第一行三个整数 n, m, k, 分别表示 DAG 的点数, 边数和参数.
接下来 m 行, 每行两个整数 ui
, vi
, 表示一条从 ui 到 vi 的有向边.
1.3 Output Format
共输出 n 行, 第 i 行一个整数, 表示 i 号点的答案

 

题目卡常。。。

基本是一道第二斯特林数得模板题。

考虑是长度len^k次方

直接套用公式i ^k = ∑s(k,j)*j!*c(i,j)

那么在toposort得时候转移i得组合数方案即可。

时间复杂度(n*k)

c++代码如下:

 

8 + 8 =