[JZOJ5511] 送你一個DAG

Description

給出一個 n 個點 m 條邊的 DAG 和參數 k。

定義一條經過 l 條邊的路徑的權值為 lk. 對于 i = 1…n, 求出所有 1 到 i 的路徑的權值之和, 對 998244353 取模.

對于前 20% 的資料, n ≤ 2000,m ≤ 5000;

對于另 10% 的資料, k = 1;

對于另 20% 的資料, k ≤ 30;

對于 100% 的資料, 1 ≤ n ≤ 100000,1 ≤ m ≤ 200000,0 ≤ k ≤ 500, 保證從 1 出發可以到達每 個點, 可能會有重邊.

Solution

設 Fi,j 表示到第i個點長度為j的路徑有多少條

直接轉移，最後算答案。

複雜度N^2

考慮優化

假設到u這個點有長度為a,b,c的三條路徑

要從 ak+bk+ck 轉移到 (a+1)k+(b+1)k+(c+1)k

二項式展開，組合數提出來

變成 ∑i=0kCik(ai+bi+ci)

與a,b,c具體無關，隻和a,b,c的i次方和有關，即當k=i時u這個點的答案

那麼狀态可以改成 Fi,j 表示i這個點當k=j時的答案

轉移是O(NK^2)的，即使用NTT優化也過不去

回到最原本的式子

Ansi=∑len(i)k

此處有關于第二類斯特林數的公式

nm=∑i=0nS(m,i)Pin

考慮其組合意義，S(m,i)表示m個有差别的球放入i個無差别的盒子中，要求盒子非空的方案數， nm 是m個有差别的球，n個有差别的盒子随便亂放，式子就是枚舉多少個盒子非空然後放球

那麼

Ansi=∑∑j=0len(i)S(k,j)Pjlen(i)

根據斯特林數的意義，j>k時顯然S為0，再把P拆成C*階乘，交換主體

=∑j=0len(i)j!S(k,j)∑Cjlen(i)

那麼現在改變狀态，設 Fi,j 表示第i個點的 ∑Cjlen(i)

根據楊輝三角，可以看出 Fi′,j=Fi,j+Fi,j−1

于是可以O(1)轉移，最後再統計答案

複雜度O(MK)

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define N 100005
#define M 505
#define mo 998244353
#define LL long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
LL f[][],s1[N],h[N];
int n,m,lim,nt[*N],fs[N],dt[*N],d[N],rd[N],mx[N],m1;
LL cf[];
void make()
{
    int l=,r=;
    fo(i,,n) if(rd[i]==) d[++r]=i;
    f[][]=;
    while(l<r)
    {
        int k=d[++l];
        for(int i=fs[k];i;i=nt[i])
        {
            int p=dt[i];
            rd[p]--;
            if(rd[p]==) d[++r]=dt[i];
            mx[p]=max(mx[p],mx[k]+);
            fo(j,,mx[k]) 
            {
                (f[p][j+]+=f[k][j])%=mo;
            }
        }
    }
    fo(i,,n)
    {
        LL s=;
        fo(j,,mx[i]) 
        {
            s=(s+f[i][j]*cf[j]%mo)%mo;
        }
        printf("%lld\n",s);
    }
}
LL ksm(LL k,LL n)
{
    LL s=;
    for(;n;k=k*k%mo,n>>=) if(n&) s=s*k%mo;
    return s;
}
void link(int x,int y)
{
    nt[++m1]=fs[x];
    dt[fs[x]=m1]=y;
}
int main()
{
    cin>>n>>m>>lim;
    fo(i,,m)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        link(x,y);
        rd[y]++;
    }
    if(lim==)
    {
        int l=,r=;
        fo(i,,n) if(rd[i]==) d[++r]=i;
        h[]=,s1[]=;
        while(l<r)
        {
            int k=d[++l];
            for(int i=fs[k];i;i=nt[i])
            {
                int p=dt[i];
                rd[p]--;
                if(rd[p]==) d[++r]=dt[i];
                s1[p]=(s1[p]+s1[k]+h[k])%mo;
                h[p]=(h[p]+h[k])%mo;
            }
        }
        fo(i,,n) printf("%lld\n",s1[i]);
    }
    else
    {
        fo(i,,n) cf[i]=ksm(i,lim);
        make();
    }   
}