题目大意
送你一个$n$个点$m$条边的DAG和参数$k$, 定义一条经过$l$条边的路径的权值为$k^l$。对于$i=1\ldots n$, 求出所有$1$到$i$的路径的权值之和, 对$998244353$取模。
题目分析
考虑，若$l=1$，这就是一个拓扑排序的问题。
若$l\gt1$，前$k\le30$的数据可以使用二项式定理展开$O(nk^2)$解决。
对于$k\le500$就要使用这里讲过的一个套路了。
使用组合数替换下降阶乘幂。
因为组合数有Pascal递推公式，则设二维状态$f[i,j]$表示到达$i$结点，经过$j$条边的权值$j$次方和。
预处理一下斯特林数与阶乘即可。
时间复杂度$O(nk)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
namespace FastIO {
const int L=1<<15;
char buf[L],*S,*T;
char getchar() {
if(S==T) {T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
return *S++;
}
int Get_Int() {
int res=0,bj=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')bj=-1;c=getchar();}
while(isdigit(c)) {res=res*10+c-'0';c=getchar();}
return res*bj;
}
}
using FastIO::Get_Int;
const int maxn=100005,maxk=505;
const int mod=998244353;
int n,m,k,InDegree[maxn];
int S[maxk][maxk],fac[maxk],f[maxn][maxk];
vector<int> edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
int main() {
n=Get_Int();
m=Get_Int();
k=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
InDegree[y]++;
}
queue<int> Q;
Q.push(1);
f[1][0]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
f[Next][0]=(f[Next][0]+f[Now][0])%mod;
for(int j=1; j<=k; j++)f[Next][j]=(1ll*f[Next][j]+f[Now][j]+f[Now][j-1])%mod;
InDegree[Next]--;
if(!InDegree[Next])Q.push(Next);
}
}
S[0][0]=fac[0]=1;
for(int i=1; i<=k; i++) {
fac[i]=1ll*fac[i-1]*i%mod;
for(int j=1; j<=i; j++)S[i][j]=(1ll*S[i-1][j]*j%mod+S[i-1][j-1])%mod;
}
for(int i=1; i<=n; i++) {
int ans=0;
for(int j=1; j<=k; j++)ans=(ans+1ll*fac[j]*S[k][j]%mod*f[i][j]%mod)%mod;
printf("%d\n",ans);
}
return 0;
}
|
