雅礼集训DAY 6 T1 xmasdag

感谢gryz的mly大好人再次给我提供了题目和数据。

和昨晚那个题几乎一样，都是x^n最后转化成第二类斯特林数*阶乘*Σ(和路径长度有关的组合数)，而因为组合数是可以利用Pascal公式实现O(1)递推的，所以最后的复杂度都降为O(NK)。

随便推一下，

ANS(x)=Σ(p是1到x的一条路径) len(p)^k = Σ(h=1 to k) S(k,h) Σ(p是1到x的一条路径)P(len(p),h)= Σ(h=1 to k) S(k,h)*h!*Σ(p是1到x的一条路径)C(len(p),h)。

所以我们设now[x][i]=Σ(p是1到x的一条路径)C(len(p),i)。

因为保证了是个DAG且1可以到达所有节点，所以图中只有1的入度是0，然后我们直接从1开始拓扑排序就行了。

需要注意的是因为这个题只是求1到x的路径，所以除了now[1][0]，其他的now[x][0]一开始都是0，而不像昨天的那个题是求树上任意一个其他点到它的路径。

(总感觉我脸黑常熟大的样子，如图)

code:

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

#include<cmath>

#define ll long long

#define maxn 100005

#define ha 998244353

#define pb push_back

using namespace std;

vector<int> g[maxn];

int ans,n,k,m,id[maxn];

int S[][],jc[];

int q[maxn],hd=,tl=;

int now[maxn][];

inline void init(){

    S[][]=,jc[]=;

    for(int i=;i<=;i++){

        jc[i]=jc[i-]*(ll)i%ha;

        for(int j=;j<=;j++) S[i][j]=((ll)S[i-][j-]+S[i-][j]*(ll)j)%ha;

    }

}

inline void solve(){

    q[++tl]=,now[][]=;

    int x,to;

    while(hd<=tl){

        x=q[hd++];

        for(int i=g[x].size()-;i>=;i--){

            to=g[x][i];

            now[to][]+=now[x][];

            if(now[to][]>=ha) now[to][]-=ha;

            for(int j=;j<=k;j++){

                now[to][j]+=now[x][j];

                if(now[to][j]>=ha) now[to][j]-=ha;

                now[to][j]+=now[x][j-];

                if(now[to][j]>=ha) now[to][j]-=ha;

            }

            if(!(--id[to])) q[++tl]=to;

        }

    }

}

int main(){

    freopen("xmasdag.in","r",stdin);

    freopen("xmasdag.out","w",stdout);

    init();

    scanf("%d%d%d",&n,&m,&k);

    int uu,vv;

    for(int i=;i<=m;i++){

        scanf("%d%d",&uu,&vv);

        g[uu].pb(vv),id[vv]++;

    }

//    for(int i=1;i<=n;i++) now[i][0]=1;

    solve();

    for(int i=;i<=n;i++){

        ans=;

        for(int j=;j<=k;j++) ans=((ll)ans+S[k][j]*(ll)jc[j]%ha*(ll)now[i][j])%ha;

        printf("%d\n",ans);

    }

    return ;

}

巴特西

雅礼集训DAY 6 T1 xmasdag

最新文章

热门文章