清华冬令营2018模拟【送你一个DAG】
first of all
蒟蒻不太会写那些运算符什么的，所以关于本题的推导公式可能不那么清晰，推荐一篇好文
1 送你一个 DAG (xmasdag.cpp/in/out, 1s, 512MB)
1.1 Description
送你一个 n 个点 m 条边的 DAG 和参数 k, 定义一条经过 l 条边的路径的权值为 lk.
对于 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 号点的答案.
分析
刚看完题目，感叹这topsort一下不就完了吗？开心。诶，手玩样例怎么玩不出来啊。仔细想想，发现是我脑回路太简单了，对于每一个点，从1到它的路径有很多方案，不同的方案长度不一定相同。而我们对于每一个点要求的是Σlen（i）^k，这个。。很恶心吧。
20 points
很简单的一种思路是，定义一个二维数组f，f【i，j】表示第i个点，从1到它的长度为j的路径条数。这个f数组可以O（m*n）求，然后对于每一个点，我们依次累加就好。
30 points
数据有一组是k=1的情况，这种情况，只需要记录从1到每个点的路径数，O（n）递推就可以了。
50 points
你看到k的范围是500，想想怎么把复杂度转到k上面。我们假设到u这个点，有三条路径，长度分别是a，b，c，那它转移到下一个点v的话，长度就分别是a+1，b+1，c+1。
那么ans v=（a+1）^k+(b+1)^k+(c+1)^k。二次项展开，合并一下，得到ΣC（k，i）*（a^i+b^i+c^i）。发现答案只与上一个点的答案有关，因此可以递推，复杂度为O（n*k^2）。
100 points
还是最初的式子，ans【i】=Σlen（i）^k。有一个有关第二类斯特林数的公式，n^m=ΣS（m，i）*P（n，i），其中S（i，j）表示将i个不同小球放到j个相同箱子（箱子不为空）的方案数，P是排列数，n^m是将m个不同小球，随意摆放在n个不同的箱子里的方案数，显然等式成立；当i<j的时候，S（i，j）为0；排列数可以转换为组合数乘阶乘，
所以ans【i】=Σ（ Σ S（k，j）*j！* C（len（i），j））=Σ S（k，j）*j！* Σ C（len（i），j）
首先斯特林数我们可以O（k*k）递推。然后求ans我们只需要再求一个Σ C（len（i），j） 就好。你发现这个东西好像可以通过杨辉三角变化一下，Σ C（len（i），j）=Σ （C（len（i）-1，j）+C（len（i）-1，j-1）），那么我们可以在topsort的时候递推即可。最后直接求答案就行。
#include<bits/stdc++.h> #define ll long long #define mod 998244353 #define maxn 1e5+5 using namespace std; char buf[1<<15],*fs,*ft; inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;} inline int read(){ int n=1,num=0; char ch=getc(); while(!isdigit(ch)) {n=(ch=='-')?-1:1;ch=getc();} while(isdigit(ch)) {num=(num<<1)+(num<<3)+(ch^48);ch=getc();} return n*num; } ll f[100010][505],g[505][505]; struct gg{int y,next;}a[300010]; int ru[100010],h[100010],link[100010]; int m,n,tot,p,z; ll ans,s; void add(int x,int y) { a[++tot].y=y;a[tot].next=link[x];link[x]=tot; } int main() { freopen("xmasdag.in","r",stdin); freopen("xmasdag.out","w",stdout); n=read();m=read();p=read(); for(int i=1;i<=m;++i) { int x=read(),y=read(); add(x,y); ++ru[y]; } h[1]=1;int head=1,tail=0; f[1][0]=1; while(head>tail) { int x=h[++tail]; for(int i=link[x];i;i=a[i].next) { int v=a[i].y; f[v][0]=(f[v][0]+f[x][0])%mod; for(int j=1;j<=p;++j) f[v][j]=(f[v][j]+(f[x][j]+f[x][j-1])%mod)%mod; --ru[v]; if(!ru[v]) h[++head]=v; } } g[0][0]=1; for(int i=1;i<=p;++i) for(int j=0;j<=p;++j) { g[i][j]=1ll*j*g[i-1][j]%mod; if(j) g[i][j]=(g[i][j]+g[i-1][j-1])%mod; } for(int i=1;i<=n;++i) { s=1;ans=0; for(int j=1;j<=p;++j) { if(j) s=(s*j)%mod; ans=(ans+((s*g[p][j])%mod)*f[i][j])%mod; } printf("%lld\n",ans); } return 0; }